InternDoor

The biggest square of ones

Mediumdynamic programming · grid

Reported in interviews at (where)

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.

Example 1
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.

Example 2
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 <= 300
  • grid[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

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.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.