Maximal Rectangle (LeetCode 85)
You're given a rows x cols binary matrix of 0 and 1 characters. Find the area of the largest rectangle made up entirely of 1's and return that area.
Worked Examples
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]6matrix = [["0"]]0"1", so no rectangle of 1s exists.matrix = [["1"]]1"1" is a rectangle of area 1.⚖️Formal Constraints & Bounds
rows == matrix.lengthcols == matrix[i].length1 <= rows, cols <= 200matrix[i][j]is'0'or'1'.
Core Insight
Do not invent a new 2D algorithm. Each row's running count of consecutive 1s upward is exactly a histogram bar height; the largest all-1s rectangle with its bottom edge on that row is the largest rectangle in that row's histogram, already solved by largestRectangleArea.
Real-World Scenario & Production Applications
Maximal contiguous free-space detection in warehouse floor-plan layouts, largest unobstructed rectangular region in image binary masks, and largest available block allocation in memory-page bitmaps.
Subproblems & Recurrence Decomposition3 Phases
For each row of the binary matrix, grow a column's running height by 1 if the cell is '1', or reset it to 0 if the cell is '0' -- this running count is exactly a histogram bar height.
heights = [0] * cols
for c in range(cols):
heights[c] = heights[c] + 1 if row[c] == "1" else 0Step-by-Step Execution Trace Table
| Row r | Matrix Row Data | Cumulative Heights Array | Monotonic Stack Max Area for Row | Global Max Rectangle Area |
|---|---|---|---|---|
| 0 | ["1", "0", "1", "0", "0"] | [1, 0, 1, 0, 0] | 1 | 1 |
| 1 | ["1", "0", "1", "1", "1"] | [2, 0, 2, 1, 1] | 3 (height 1, width 3) | 3 |
| 2 | ["1", "1", "1", "1", "1"] | [3, 1, 3, 2, 2] | 6 (height 2, width 3) | 6 |
| 3 | ["1", "0", "0", "1", "0"] | [4, 0, 0, 3, 0] | 4 (height 4, width 1) | 6 |
| 1 | cols = len(matrix[0]) |
| 2 | heights = [0] * cols |
| 3 | best = 0 |
| 4 | for row in matrix: |
| 5 | for c in range(cols): |
| 6 | heights[c] = heights[c] + 1 if row[c] == "1" else 0 |
| 7 | best = max(best, largestRectangleArea(heights)) |
| 8 | return best |
Conceptual Narrative
Maximal Rectangle reduces a 2D binary matrix into a sequence of 1D histogram subproblems, reusing the monotonic stack algorithm to find the global maximal area in O(M x N) time.
🧭 Conceptual Foundation & Pattern Intuition
Given an binary matrix of '0's and '1's, we want to find the largest rectangle containing only '1's.
A 2D brute force testing all pairs of top-left and bottom-right corners costs .
The breakthrough is recognizing that every row in the matrix can serve as the ground baseline of a histogram:
- We maintain a 1D array
heightsof size (number of columns). - As we iterate through the matrix row by row:
- If
matrix[r][c] == '1', the height of that column increases:heights[c] += 1. - If
matrix[r][c] == '0', the continuous column of ones is broken at this row: the bar resets to ground level:heights[c] = 0.
- If
- After updating
heightsfor row , the largest rectangle whose base sits on row is precisely the Largest Rectangle in Histogram for arrayheights! - Running the monotonic stack histogram algorithm on each row evaluates all possible rectangle bases in time per row, resolving the entire matrix in total time.
🧱 The Analogy: Stacking Bricks Row by Row into a Skyline
Imagine walking through a warehouse from the ceiling down to the floor, scanning one horizontal shelf at a time. For each vertical column, you ask: "How many consecutive solid bricks are stacked directly above this shelf?" That count is the height of a building in a skyline. A missing brick ('0') collapses the building to zero height at that shelf. At each shelf, you run your skyline scanner (the monotonic stack histogram solver) to find the largest billboard you could hang on that row's buildings.
🔑 Why It Works
The reduction is seamless: no new geometric rectangle logic is required. By transforming 2D consecutive ones into dynamic 1D heights, the monotonic stack solves an NP-hard-looking 2D problem in optimal linear time.
Resetting column height to 0 on
'0'character: In the cumulative histogram reduction, ifmatrix[r][c] == '0', the column height must reset to 0 (heights[c] = 0). Forgetting to reset treats disconnected 1s as tall continuous bars.String characters vs integers: Matrix cells contain string
'1'and'0'. Comparing with integer1or failing to increment integer heights causes bugs.Running largest rectangle in histogram per row: Re-running the monotonic stack histogram algorithm on each row reduces the 2D problem to 1D histogram problems in optimal time.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Largest all-1s rectangle inside a 2D binary matrix; a natural escalation of a histogram problem already mastered in this group.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after processing row r, heights[c] equals the number of consecutive 1s ending at row r in column c — exactly a histogram bar height for that row's 'ground level'.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Resetting a column's height to 0 only sometimes: any '0' cell must fully reset that column's running count, not decrement it.
Re-deriving a new rectangle algorithm from scratch instead of reusing largestRectangleArea unchanged on each row's heights.
Comparing character '1' against integer 1 without the explicit string check, silently treating every cell as truthy.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I keep a
heightsarray of lengthcols, all zero. For each row, I updateheights[c] = heights[c] + 1 if row[c] == '1' else 0, then call the already-masteredlargestRectangleArea(heights)and keep the running max. Each row's largest all-1s rectangle with its bottom edge on that row is exactly the largest rectangle in that row's histogram. Runs in O(rows * cols) time and O(cols) space."
Complexity & Mathematical Proof
O(rows * cols)
Look at the nested structure: the outer loop visits each of the rows rows once. For each row, updating the heights array is O(cols). Calling largestRectangleArea(heights) on that row's heights array runs in amortized O(cols) time, by the same push/pop-at-most-once monotonic stack argument already proven for Largest Rectangle in Histogram earlier in this group. Multiplying rows iterations by O(cols) work per row yields O(rows * cols) total time.
O(cols) Auxiliary
Look at memory allocation: the heights array persists across rows and is reused in place, costing O(cols). The monotonic stack allocated fresh inside each call to largestRectangleArea also costs at most O(cols) and is discarded after each row. No additional per-row accumulation is kept, so total auxiliary space is O(cols), independent of rows.
Derivation Progression
heights[c] = heights[c] + 1 if row[c] == '1' else 0
Rebuilding the histogram heights for one row costs O(cols).
Reuses the amortized O(N) monotonic-stack histogram solver already proven in this group, with N = cols.
Summing the O(cols) work performed once per row over all rows gives the total bound.
Variable Definitions
Number of rows in the binary matrix
Number of columns in the binary matrix
Memory Architecture & Bounds
O(1) Iterative outer loop with zero recursion frames
O(cols) Persistent heights array plus a per-row monotonic stack of at most cols entries
O(1) Scalar running best-area integer
Boundary Best / Worst Cases
all-zero or all-one matrix (stack still bounded by cols per row).
.
any matrix shape, since every row runs its own O(cols) histogram solve regardless of content.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximal rectangle containing only 1's in a binary matrix". Dimensionality reduction: a 2D grid problem can be decomposed into separate instances of 1D Largest Rectangle in Histogram (LC 84).
. Time budget: , running in ms.
Empty matrix ( or ). Resetting heights to 0 on '0's rather than decrementing.
Maximal Rectangle (LeetCode 85)
You're given a rows x cols binary matrix of 0 and 1 characters. Find the area of the largest rectangle made up entirely of 1's and return that area.
Worked Examples
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]6matrix = [["0"]]0"1", so no rectangle of 1s exists.matrix = [["1"]]1"1" is a rectangle of area 1.⚖️Formal Constraints & Bounds
rows == matrix.lengthcols == matrix[i].length1 <= rows, cols <= 200matrix[i][j]is'0'or'1'.
Core Insight
Do not invent a new 2D algorithm. Each row's running count of consecutive 1s upward is exactly a histogram bar height; the largest all-1s rectangle with its bottom edge on that row is the largest rectangle in that row's histogram, already solved by largestRectangleArea.
Real-World Scenario & Production Applications
Maximal contiguous free-space detection in warehouse floor-plan layouts, largest unobstructed rectangular region in image binary masks, and largest available block allocation in memory-page bitmaps.
Subproblems & Recurrence Decomposition3 Phases
For each row of the binary matrix, grow a column's running height by 1 if the cell is '1', or reset it to 0 if the cell is '0' -- this running count is exactly a histogram bar height.
heights = [0] * cols
for c in range(cols):
heights[c] = heights[c] + 1 if row[c] == "1" else 0Step-by-Step Execution Trace Table
| Row r | Matrix Row Data | Cumulative Heights Array | Monotonic Stack Max Area for Row | Global Max Rectangle Area |
|---|---|---|---|---|
| 0 | ["1", "0", "1", "0", "0"] | [1, 0, 1, 0, 0] | 1 | 1 |
| 1 | ["1", "0", "1", "1", "1"] | [2, 0, 2, 1, 1] | 3 (height 1, width 3) | 3 |
| 2 | ["1", "1", "1", "1", "1"] | [3, 1, 3, 2, 2] | 6 (height 2, width 3) | 6 |
| 3 | ["1", "0", "0", "1", "0"] | [4, 0, 0, 3, 0] | 4 (height 4, width 1) | 6 |
| 1 | cols = len(matrix[0]) |
| 2 | heights = [0] * cols |
| 3 | best = 0 |
| 4 | for row in matrix: |
| 5 | for c in range(cols): |
| 6 | heights[c] = heights[c] + 1 if row[c] == "1" else 0 |
| 7 | best = max(best, largestRectangleArea(heights)) |
| 8 | return best |
Conceptual Narrative
Maximal Rectangle reduces a 2D binary matrix into a sequence of 1D histogram subproblems, reusing the monotonic stack algorithm to find the global maximal area in O(M x N) time.
🧭 Conceptual Foundation & Pattern Intuition
Given an binary matrix of '0's and '1's, we want to find the largest rectangle containing only '1's.
A 2D brute force testing all pairs of top-left and bottom-right corners costs .
The breakthrough is recognizing that every row in the matrix can serve as the ground baseline of a histogram:
- We maintain a 1D array
heightsof size (number of columns). - As we iterate through the matrix row by row:
- If
matrix[r][c] == '1', the height of that column increases:heights[c] += 1. - If
matrix[r][c] == '0', the continuous column of ones is broken at this row: the bar resets to ground level:heights[c] = 0.
- If
- After updating
heightsfor row , the largest rectangle whose base sits on row is precisely the Largest Rectangle in Histogram for arrayheights! - Running the monotonic stack histogram algorithm on each row evaluates all possible rectangle bases in time per row, resolving the entire matrix in total time.
🧱 The Analogy: Stacking Bricks Row by Row into a Skyline
Imagine walking through a warehouse from the ceiling down to the floor, scanning one horizontal shelf at a time. For each vertical column, you ask: "How many consecutive solid bricks are stacked directly above this shelf?" That count is the height of a building in a skyline. A missing brick ('0') collapses the building to zero height at that shelf. At each shelf, you run your skyline scanner (the monotonic stack histogram solver) to find the largest billboard you could hang on that row's buildings.
🔑 Why It Works
The reduction is seamless: no new geometric rectangle logic is required. By transforming 2D consecutive ones into dynamic 1D heights, the monotonic stack solves an NP-hard-looking 2D problem in optimal linear time.
Resetting column height to 0 on
'0'character: In the cumulative histogram reduction, ifmatrix[r][c] == '0', the column height must reset to 0 (heights[c] = 0). Forgetting to reset treats disconnected 1s as tall continuous bars.String characters vs integers: Matrix cells contain string
'1'and'0'. Comparing with integer1or failing to increment integer heights causes bugs.Running largest rectangle in histogram per row: Re-running the monotonic stack histogram algorithm on each row reduces the 2D problem to 1D histogram problems in optimal time.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Largest all-1s rectangle inside a 2D binary matrix; a natural escalation of a histogram problem already mastered in this group.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after processing row r, heights[c] equals the number of consecutive 1s ending at row r in column c — exactly a histogram bar height for that row's 'ground level'.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Resetting a column's height to 0 only sometimes: any '0' cell must fully reset that column's running count, not decrement it.
Re-deriving a new rectangle algorithm from scratch instead of reusing largestRectangleArea unchanged on each row's heights.
Comparing character '1' against integer 1 without the explicit string check, silently treating every cell as truthy.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I keep a
heightsarray of lengthcols, all zero. For each row, I updateheights[c] = heights[c] + 1 if row[c] == '1' else 0, then call the already-masteredlargestRectangleArea(heights)and keep the running max. Each row's largest all-1s rectangle with its bottom edge on that row is exactly the largest rectangle in that row's histogram. Runs in O(rows * cols) time and O(cols) space."
Complexity & Mathematical Proof
O(rows * cols)
Look at the nested structure: the outer loop visits each of the rows rows once. For each row, updating the heights array is O(cols). Calling largestRectangleArea(heights) on that row's heights array runs in amortized O(cols) time, by the same push/pop-at-most-once monotonic stack argument already proven for Largest Rectangle in Histogram earlier in this group. Multiplying rows iterations by O(cols) work per row yields O(rows * cols) total time.
O(cols) Auxiliary
Look at memory allocation: the heights array persists across rows and is reused in place, costing O(cols). The monotonic stack allocated fresh inside each call to largestRectangleArea also costs at most O(cols) and is discarded after each row. No additional per-row accumulation is kept, so total auxiliary space is O(cols), independent of rows.
Derivation Progression
heights[c] = heights[c] + 1 if row[c] == '1' else 0
Rebuilding the histogram heights for one row costs O(cols).
Reuses the amortized O(N) monotonic-stack histogram solver already proven in this group, with N = cols.
Summing the O(cols) work performed once per row over all rows gives the total bound.
Variable Definitions
Number of rows in the binary matrix
Number of columns in the binary matrix
Memory Architecture & Bounds
O(1) Iterative outer loop with zero recursion frames
O(cols) Persistent heights array plus a per-row monotonic stack of at most cols entries
O(1) Scalar running best-area integer
Boundary Best / Worst Cases
all-zero or all-one matrix (stack still bounded by cols per row).
.
any matrix shape, since every row runs its own O(cols) histogram solve regardless of content.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximal rectangle containing only 1's in a binary matrix". Dimensionality reduction: a 2D grid problem can be decomposed into separate instances of 1D Largest Rectangle in Histogram (LC 84).
. Time budget: , running in ms.
Empty matrix ( or ). Resetting heights to 0 on '0's rather than decrementing.