InternDoor

The biggest rectangle of ones

Hardstack · dynamic programming · grid

Reported in interviews at (where)

grid holds only 0s and 1s.

Return the area of the largest rectangle, with its sides along the grid lines, that holds nothing but 1s. The area is its number of cells.

Example 1
Input
grid = [[1,0,1,1],[1,1,1,1],[0,1,1,1]]
Output
6

Rows 1 and 2, columns 1 to 3, are all 1s: 2 x 3 = 6.

Example 2
Input
grid = [[0]]
Output
0

There are no 1s at all.

Limits

  • 1 <= m, n <= 200
  • grid[i][j] is 0 or 1

Hints

Hint 1

Go row by row, keeping for each column how many 1s in a row end at the current row. That is a histogram.

Hint 2

The largest rectangle under a histogram comes from a stack of bars of increasing height: when a lower bar arrives, pop the taller ones and measure each.

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.