Largest 1-Bordered Square

MediumMatrixprefix sum

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given a grid grid of 0s and 1s, find the largest square sub-grid whose entire border (its four edges) consists of 1s. The inside of the square does not matter. Return the number of cells in that square (its side length squared), or 0 if the grid contains no 1 at all.

Examples

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9
The full 3x3 grid has an all-ones border even though its center is 0.
Input: grid = [[1,1,0,0]]
Output: 1
No 2x2 square fits in a single row, but a single `1` is a 1x1 square.

Constraints

  • 1 <= grid.length, grid[0].length <= 100
  • grid[i][j] is 0 or 1

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More prefix sum problems