Count All-Lit Rectangles
HardMatrix
Problem
An LED wall is an m × n grid where 1 is a working LED and 0 a dead one. A designer can display a solid shape on any axis-aligned rectangle made only of working LEDs.
Return the number of such rectangles. Rectangles are distinct when they differ in at least one of their four sides; a single LED counts as a rectangle.
Example 1
- Input:
- grid = [[1, 0, 1], [1, 1, 0], [1, 1, 0]]
- Output:
- 13
6 single LEDs, 2 horizontal pairs (rows 1 and 2), 4 vertical runs (three in column 0, one in column 1) and one 2 × 2 block: 6 + 2 + 4 + 1 = 13.
Example 2
- Input:
- grid = [[1, 1, 1]]
- Output:
- 6
Three singles, two pairs and one triple.
Constraints
- 1 ≤ m, n ≤ 150
- grid[i][j] is 0 or 1
- The answer fits in a 32-bit signed integer.
Hint
Show the first hint
Count rectangles by their bottom-right corner. For a fixed bottom row, turn each column into a bar: the number of consecutive 1s ending at that row.
Walkthrough
How to approach it
01Clarify before coding
- Do overlapping rectangles count separately? Yes, every distinct choice of four sides counts.
- Does a single LED count? Yes, it is a 1 × 1 rectangle.
- How large can the answer be? Up to about 1.3 · 10^8 for a 150 × 150 all-ones grid, so it fits in 32 bits.
02Brute force
Enumerate every rectangle (two rows, two columns) and check with a 2-D prefix sum whether its sum equals its area.
Cost: O(m² · n²): about 5 · 10^8 rectangles for 150 × 150, far too slow.
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.