Maximum Rectangles
HardA histogram per row
Problem
Given a binary matrix, find the largest rectangle of all 1s.
Build a histogram of 1-heights per row and run largest-rectangle-in-histogram on each.
The idea
Treat each row as the base of a histogram whose bar heights are the counts of consecutive 1s ending at that row. Running the largest-rectangle-in-histogram routine on every row gives the answer in O(rows × cols).
The trick
- Height resets to 0 on a 0, otherwise it grows by 1.
- One histogram pass per row; the heights carry over between rows.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] Values: 1, 0, 1, 0, 0.
1for each row: update heights[j] (reset to 0 on a 0)2ans = max(ans, largestRectangleInHistogram(heights))Input
- array
- [1, 0, 1, 0, 0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
- Output:
- 6
- Explanation:
- The biggest all-1 rectangle has area 6.
Example 2
- Input:
- matrix = [[0,1],[1,1]]
- Output:
- 2
- Explanation:
- The two right 1s form area 2.
Example 3
- Input:
- matrix = [[0]]
- Output:
- 0
- Explanation:
- No 1s → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.