Largest Lit Rectangle
HardStack
Problem
A billboard is a grid of bulbs; grid[r][c] is 1 if the bulb works and 0 if it is broken.
Return the area of the largest axis-aligned rectangle made only of working bulbs.
Example 1
- Input:
- grid = [[1, 0, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]]
- Output:
- 6
Rows 1–2 and columns 1–3 are all lit: 2 · 3 = 6 (columns 2–3 over all three rows also give 6).
Example 2
- Input:
- grid = [[0]]
- Output:
- 0
Constraints
- 1 ≤ rows, cols ≤ 200
- grid[r][c] is 0 or 1
Hint
Show the first hint
Fix the bottom row of the rectangle. What does the grid look like above that row?
Walkthrough
How to approach it
01Clarify before coding
- Must the rectangle be axis-aligned and solid? Yes, only working bulbs inside.
- Can the grid be all zeros? Yes, return 0.
- Grid size? Up to 200 × 200, so O(rows · cols) or O(rows · cols²) both pass, but aim for the linear one.
02Brute force
Try every top-left and bottom-right corner pair and check (with a 2-D prefix sum) whether the rectangle is all ones.
Cost: O(R² · C²) corner pairs: 1.6·10^9 for a 200 × 200 grid.
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.