The biggest square of ones
grid holds only 0s and 1s.
Return the area of the largest square, with its sides along the grid lines, that holds nothing but 1s.
- Input
grid = [[1,0,1,1],[1,1,1,1],[0,1,1,1]]- Output
4
Several 2 x 2 squares fit, such as rows 1 and 2 with columns 2 and 3. No 3 x 3 square does.
- Input
grid = [[0,1],[1,0]]- Output
1
The 1s never touch side by side, so a single cell is the best square.
Limits
1 <= m, n <= 300grid[i][j] is 0 or 1
Hints
Hint 1
Let side[i][j] be the side of the largest all-1 square whose bottom-right corner is (i, j).
Hint 2
For a 1 cell, side[i][j] is 1 plus the smallest of the values above, to the left and diagonally above-left. One row of them is enough to keep.
Where this was reported
- Flipkart, SDE-1 interview, 2025 (PrepInsta)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
