Maximal Rectangle LeetCode 85 Guide

LeetCode 85 — Maximal Rectangle — gives you an m x n binary matrix filled with characters '0' and '1'. Your task is to find the largest rectangle containing only 1s and return its area. The rectangle must be axis-aligned, and it can span any number of consecutive rows and columns as long as every cell in the rectangle contains a '1'.

The brute-force approach tries all pairs of top-left and bottom-right corners, but with up to 200 rows and 200 columns this is far too slow. The optimal solution leverages a classic reduction: because any maximal rectangle must have a bottom row, we can fix the bottom row and ask "what is the largest rectangle whose bottom edge lies on this row?" — a question that can be answered in O(n) per row.

At first glance, this seems like a 2D dynamic programming problem, but the breakthrough insight is that it reduces to running the 1D Largest Rectangle in Histogram algorithm (LeetCode 84) exactly m times — once per row. Understanding this reduction is the entire algorithm.

The key insight is that each row of the binary matrix can be treated as the base of a histogram. Define heights[j] as the number of consecutive 1s directly above and including row i at column j. If matrix[i][j] is '0', the consecutive run is broken and heights[j] resets to 0. If matrix[i][j] is '1', heights[j] increments by 1 from its value at the previous row.

With this definition, the heights array after processing row i describes a histogram where each bar of height heights[j] represents a vertical strip of 1s in column j that reaches down to row i. The largest rectangle whose bottom edge lies on row i is exactly the largest rectangle that fits within this histogram — which is precisely what LeetCode 84 solves.

Applying this reduction m times (once per row) and tracking the maximum area found across all rows gives the correct answer. Each row's histogram is computed incrementally in O(n) by updating the heights array from the previous row, and the LeetCode 84 monotonic stack sweep on that histogram also takes O(n). Total time: O(m * n).

Initialize a heights array of length n to all zeros before processing any row. This represents the histogram state before row 0 — no consecutive 1s have been seen yet. Then iterate row by row from 0 to m-1, updating the heights array in a single O(n) pass per row.

For each column j in the current row: if matrix[i][j] == '1', increment heights[j] by 1 (extending the consecutive run of 1s downward); if matrix[i][j] == '0', reset heights[j] to 0 (the run is broken). After updating all columns, pass the heights array to the LeetCode 84 subroutine and take the maximum of the returned area and the running global maximum.

The heights array captures exactly the information needed: at any row i, heights[j] is the number of rows (including row i) looking upward from row i that are all 1 in column j. A bar of height h at column j means there is a h-row vertical strip of 1s ending at row i in that column. The histogram formed by all such bars encodes every possible rectangle with bottom edge on row i.

The LeetCode 84 subroutine uses a monotonic increasing stack of column indices. Iterate through the heights array left to right, maintaining the invariant that the stack always contains indices of bars in non-decreasing height order. When a bar shorter than the stack top is encountered, pop the stack top and compute the area of the rectangle it could form — using the popped height and the width derived from the current index and the new stack top.

Concretely: for each index i, while the stack is non-empty and heights[stack top] > heights[i], pop index j. Compute height = heights[j]. Compute width = i - stack[-1] - 1 if the stack is still non-empty, else i. Update max_area = max(max_area, height * width). Then push i. Appending a sentinel value of 0 at the end of heights ensures all remaining bars are flushed from the stack during the main loop without a separate post-loop pass.

Each bar is pushed once and popped once, so the inner while loop does O(n) total work across all iterations of the outer for loop. The entire subroutine is O(n) time and O(n) space for the stack. Calling it once per row gives O(m * n) total time and O(n) space — only the heights array and stack are needed, not any 2D structure.

Consider the classic 4x5 binary matrix: row 0 = [1,0,1,0,0], row 1 = [1,0,1,1,1], row 2 = [1,1,1,1,1], row 3 = [1,0,0,1,0]. We initialize heights = [0,0,0,0,0] and process each row in turn.

After row 0: heights = [1,0,1,0,0]. Running LeetCode 84 on this histogram finds max rectangle area = 1. After row 1: heights = [2,0,2,1,1]. LeetCode 84 finds area = 3 (the three-wide rectangle of height 1 spanning columns 2-4). After row 2: heights = [3,1,3,2,2]. LeetCode 84 finds area = 6 (the three-wide rectangle of height 2 spanning columns 2-4, or other combinations — the global max is 6). After row 3: heights = [4,0,0,3,0]. LeetCode 84 finds area = 4.

The global maximum across all rows is 6, which is the correct answer. The 6-cell rectangle is the 2-row by 3-column block of 1s at rows 1-2, columns 2-4. Notice how the heights array naturally encodes this: at row 2, heights[2..4] = [3,2,2], and the LeetCode 84 algorithm correctly identifies that a rectangle of height 2 spanning width 3 (area 6) fits within this histogram.

Python solution: def maximalRectangle(matrix): if not matrix: return 0; m, n = len(matrix), len(matrix[0]); heights = [0] * n; max_area = 0; for i in range(m): for j in range(n): heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0; max_area = max(max_area, largestRectangleArea(heights[:])); return max_area. The largestRectangleArea helper uses the sentinel-0 monotonic stack from LeetCode 84. Note: heights[:] passes a copy to avoid the helper's in-place append(0) mutating the array used across rows — or the helper can avoid mutating by using a local variable.

Java solution: public int maximalRectangle(char[][] matrix) { int m = matrix.length, n = matrix[0].length; int[] heights = new int[n]; int max = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0; } max = Math.max(max, largestRectangleArea(heights)); } return max; }. The largestRectangleArea helper is a standard LeetCode 84 implementation with a Deque-based monotonic stack and a sentinel 0 appended to a copy of heights.

Time complexity: O(m * n) — two nested loops for heights updates (O(m*n) total) plus m calls to largestRectangleArea each costing O(n) (O(m*n) total). Space complexity: O(n) for the heights array and stack. The solution is clean and directly reuses the LeetCode 84 subroutine without modification, making it easy to test and maintain.

Largest Rectangle in Histogram (LeetCode 84) is the direct foundation of this problem — understanding its monotonic stack solution is a prerequisite. Maximal Square (LeetCode 221) solves a closely related problem: finding the largest square (not rectangle) of 1s. It uses a 2D DP approach where dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, representing the side length of the largest square with its bottom-right corner at (i,j). The two problems together cover the major "largest region of 1s" question family.

Set Matrix Zeroes (LeetCode 73) is another matrix manipulation problem that requires careful in-place updates — when a 0 is found, entire rows and columns must be zeroed without using extra space. It reinforces the pattern of reading the matrix in multiple passes and using constant-space markers. Together with Maximal Rectangle, it builds the skill of processing a binary matrix efficiently without unnecessary auxiliary storage.

The matrix + stack family appears frequently in hard-level coding interviews. A strong approach is to master LeetCode 84 first (monotonic stack on a 1D array), then LeetCode 85 (apply 84 row by row on a 2D matrix), then Trapping Rain Water (LeetCode 42, another monotonic stack area problem). These three problems share the core idea of using a stack to defer area calculations until boundary information is known, and together they represent the full scope of stack-based area computation questions.