Largest Solid Rectangle
Problem
A floor plan is a binary grid plan, where 1 is free floor and 0 is a pillar or wall. Find the largest rectangle, aligned with the grid, made entirely of free floor, and return its area.
The rectangle does not need to be square.
Example 1
- Input:
- plan = [[0, 1, 1, 0, 1], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 1, 1, 1]]
- Output:
- 8
Rows 1–2, columns 0–3 form a 2 × 4 block of free floor.
Example 2
- Input:
- plan = [[0, 1], [1, 0]]
- Output:
- 1
Constraints
- 1 ≤ plan.length, plan[0].length ≤ 200
- plan[r][c] is 0 or 1
Hint
Show the first hint
Fix the bottom row of the rectangle. For each column, how tall a run of 1s ends at that row?
Walkthrough
How to approach it
01Clarify before coding
- Square or any rectangle? Any axis-aligned rectangle.
- Return the area? Yes, the number of cells.
- Is a single free cell a rectangle? Yes, area 1.
02Brute force
Try every pair of corners and check whether the rectangle is all 1s, or use a 2-D prefix sum to check each one in O(1).
Cost: O(m² · n²) rectangles even with prefix sums: about 1.6 · 10^9 for 200 × 200.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.