Maximal Rectangle [Hard] — Histogram Stack per Row

Problem Statement#

LeetCode 85 — Maximal Rectangle (Hard)

Given a 2D binary matrix filled with '0's and '1's, find the largest rectangle containing only '1's and return its area.

Example:

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 largest rectangle of all 1s is 2 rows tall and 3 columns wide (rows 2–3, columns 2–4), giving area = 6.

Constraints:

• rows == matrix.length
• cols == matrix[0].length
• 1 <= rows, cols <= 200
• matrix[i][j] is '0' or '1'

Why This Problem Matters#

Maximal Rectangle is a classic "hard" that shows up at Amazon, Microsoft, Google, and Meta — and for good reason. It combines two important ideas:

1. Dynamic programming to reduce a 2D problem to a series of 1D problems row by row.
2. Monotonic stack (from LC 84) to solve each 1D histogram sub-problem in linear time.

If you've already solved LC 84 (Largest Rectangle in Histogram), LC 85 is its natural 2D extension. The bridge between them is the row-as-histogram insight — the single observation that unlocks the entire solution.

Beyond just LeetCode, this pattern — collapsing rows into a running histogram and processing column heights — reappears in:

• Counting maximal rectangles of a given colour in image processing
• Finding the widest obstacle-free corridor in grid-based pathfinding
• Data warehouse column-packing optimizations

Understanding this problem deeply means you understand how to decompose hard 2D geometry problems into manageable 1D passes, a skill that transfers directly to system design and algorithm interviews.

The Row-as-Histogram Insight#

The breakthrough observation is simple to state, but profound:

For every row i, treat the matrix as a histogram where each bar's height equals the number of consecutive '1's ending at row i in that column.

Let's make this concrete. Define heights[j] as the height of the histogram bar at column j when we are processing row i:

• If matrix[i][j] == '1', then heights[j] = heights[j] + 1 (extend the bar downward).
• If matrix[i][j] == '0', then heights[j] = 0 (the run of 1s is broken; reset).

After updating heights for row i, we have a valid histogram. The largest rectangle in that histogram is a candidate for the global answer. We take the maximum over all rows.

This works because any rectangle of 1s in the matrix must have a bottom row. When we process that bottom row, the histogram faithfully encodes exactly how tall the consecutive run of 1s is in each column — which is exactly the information we need to find rectangles.

So the algorithm becomes:

1. Maintain a heights array of length n (number of columns), initialised to all zeros.
2. For each row, update heights using the rule above.
3. Run the Largest Rectangle in Histogram algorithm on the current heights.
4. Track the global maximum area seen across all rows.

The Largest Rectangle in Histogram algorithm (LC 84) itself runs in O(n) using a monotonic stack. Since we do this for each of the m rows, total time is O(m × n).

Visual Dry Run#

Let's trace through the example step by step.

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"]

After processing Row 0:

Heights array: [1, 0, 1, 0, 0]

Histogram:

col:   0  1  2  3  4
       █     █

Largest rectangle in this histogram: 1 (single bars of height 1). max_area = 1

After processing Row 1:

• Col 0: matrix[1][0]='1' → 1 + 1 = 2
• Col 1: matrix[1][1]='0' → reset to 0
• Col 2: matrix[1][2]='1' → 1 + 1 = 2
• Col 3: matrix[1][3]='1' → 0 + 1 = 1
• Col 4: matrix[1][4]='1' → 0 + 1 = 1

Heights array: [2, 0, 2, 1, 1]

Histogram:

col:   0  1  2  3  4
       █     █
       █     █  █  █

Largest rectangle: cols 2–4 at height 1 → area = 3. Or col 0 alone at height 2 → area = 2. Or col 2 alone at height 2 → area = 2. Best = 3. max_area = 3

After processing Row 2:

• Col 0: '1' → 2 + 1 = 3
• Col 1: '1' → 0 + 1 = 1
• Col 2: '1' → 2 + 1 = 3
• Col 3: '1' → 1 + 1 = 2
• Col 4: '1' → 1 + 1 = 2

Heights array: [3, 1, 3, 2, 2]

Histogram:

col:   0  1  2  3  4
       █     █
       █     █  █  █
       █  █  █  █  █

Now run the histogram algorithm:

• The widest rectangle at height 1 spans all 5 cols → area = 5.
• The rectangle at height 2 spans cols 2–4 → area = 6.
• The rectangle at height 3 spans cols 0 and 2 separately → area = 3 each.

Best = 6. max_area = 6

After processing Row 3:

• Col 0: '1' → 3 + 1 = 4
• Col 1: '0' → reset to 0
• Col 2: '0' → reset to 0
• Col 3: '1' → 2 + 1 = 3
• Col 4: '0' → reset to 0

Heights array: [4, 0, 0, 3, 0]

Histogram:

col:   0  1  2  3  4
       █           
       █        █  
       █        █  
       █        █  

Largest rectangle: col 0 alone at height 4 → area = 4. Col 3 alone at height 3 → area = 3. Best = 4. max_area stays at 6.

Final answer: 6

Common Mistakes#

1. Forgetting to reset heights to 0 on a '0' cell#

A very common error is writing something like:

heights[j] = heights[j] + 1 if row[j] == '1' else heights[j]

That leaves stale heights from previous rows in columns where the current cell is '0'. The histogram would then include phantom bars that do not correspond to real runs of 1s, producing inflated — wrong — answers. Always reset: heights[j] = 0 when matrix[i][j] == '0'.

2. Off-by-one errors in the width calculation inside the histogram algorithm#

When popping a bar from the stack to compute its rectangle's width, the left boundary is the new stack top (after popping), not the popped index itself. The formula is:

width = i - stack[-1] - 1   # if stack is non-empty
width = i                   # if stack is empty (bar extends all the way to the left)

A fence-post error here silently produces areas that are one column too narrow or too wide.

3. Mutating the heights array before passing it to the histogram function#

The histogram algorithm in LC 84 often appends a sentinel 0 at the end of the array to flush remaining bars. If you pass heights directly and the function mutates it (by appending in place), the sentinel persists into the next row's update. Always work on a copy, or remove the sentinel afterward, or use the enumerate-based approach that does not mutate the array.

4. Initialising heights once outside the loop vs. once per row#

heights should be a single array of length n initialised to all zeros before the row loop. It is then updated (not reinitialised) every row — this is the entire DP mechanism. Reinitialising it inside the loop destroys the accumulated column heights from previous rows and breaks the algorithm.

5. Treating the matrix as integers instead of strings#

LeetCode 85's input uses '0' and '1' as strings, not integers. A check like row[j] == 1 (integer) will always be False, so all heights stay at zero. Double-check the character comparison: row[j] == '1'.

Solutions#

Approach: Row-by-Row Histogram + Monotonic Stack#

Both solutions below implement the same algorithm:

• Build/update the heights array as a DP step.
• For each row, run the largest_rectangle_in_histogram sub-routine (LC 84 logic) using a monotonic stack.
• Track the global maximum area.

Python#

from typing import List
 
def maximalRectangle(matrix: List[List[str]]) -> int:
    # Edge case: empty matrix
    if not matrix or not matrix[0]:
        return 0
 
    rows, cols = len(matrix), len(matrix[0])
 
    # heights[j] = number of consecutive '1's ending at the current row in column j
    heights = [0] * cols
    max_area = 0
 
    def largest_rectangle_in_histogram(h: List[int]) -> int:
        """
        LC 84 — Largest Rectangle in Histogram using a monotonic (increasing) stack.
        Appends a sentinel 0 so every bar is eventually popped and processed.
        """
        # Sentinel 0 at the end forces all remaining bars to be evaluated
        h = h + [0]
        stack = []   # stores indices of bars in increasing height order
        best = 0
 
        for i, height in enumerate(h):
            # While the current bar is shorter than the bar at the stack's top,
            # pop and calculate the area of the rectangle whose height is the popped bar
            while stack and height < h[stack[-1]]:
                popped_height = h[stack.pop()]   # height of the rectangle
 
                if stack:
                    # Left boundary: the new top of the stack after popping
                    width = i - stack[-1] - 1
                else:
                    # Stack is empty: rectangle extends all the way to the left
                    width = i
 
                best = max(best, popped_height * width)
 
            # Push current index; stack remains sorted by increasing height
            stack.append(i)
 
        return best
 
    for row in matrix:
        for j in range(cols):
            if row[j] == '1':
                # Extend the column's consecutive run of 1s downward
                heights[j] += 1
            else:
                # A '0' breaks the run; reset this column's height
                heights[j] = 0
 
        # Treat the updated heights array as a histogram and find its largest rectangle
        max_area = max(max_area, largest_rectangle_in_histogram(heights))
 
    return max_area

JavaScript#

/**
 * @param {character[][]} matrix
 * @return {number}
 */
function maximalRectangle(matrix) {
    // Edge case: empty matrix
    if (!matrix.length || !matrix[0].length) return 0;
 
    const rows = matrix.length;
    const cols = matrix[0].length;
 
    // heights[j] tracks consecutive '1's ending at current row in column j
    const heights = new Array(cols).fill(0);
    let maxArea = 0;
 
    /**
     * LC 84 — Largest Rectangle in Histogram using a monotonic stack.
     * Appends a sentinel 0 to ensure all bars are processed.
     */
    function largestRectangleInHistogram(h) {
        // Create a copy with a sentinel 0 appended to flush all bars at the end
        const hist = [...h, 0];
        const stack = [];  // monotonic increasing stack of indices
        let best = 0;
 
        for (let i = 0; i < hist.length; i++) {
            // Pop bars taller than the current bar and calculate their rectangle area
            while (stack.length > 0 && hist[i] < hist[stack[stack.length - 1]]) {
                const poppedHeight = hist[stack.pop()];  // height of the candidate rectangle
 
                // Width depends on whether there's a left boundary in the stack
                const width = stack.length > 0
                    ? i - stack[stack.length - 1] - 1   // left boundary exists
                    : i;                                  // extends all the way to left
 
                best = Math.max(best, poppedHeight * width);
            }
 
            // Push index; stack always holds indices with non-decreasing heights
            stack.push(i);
        }
 
        return best;
    }
 
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                // Grow the bar: consecutive 1s from above continue through this cell
                heights[j] += 1;
            } else {
                // Reset: a 0 breaks the column's run of 1s
                heights[j] = 0;
            }
        }
 
        // Each updated histogram is a candidate — find its best rectangle
        maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
    }
 
    return maxArea;
}

Complexity Analysis#

This is optimal — we cannot do better than O(m × n) because every cell must be read at least once to determine whether it is part of the maximal rectangle.

Follow-up Questions#

Interviewers often extend this problem. Here are the most common follow-ups with brief guidance:

LC 84 — Largest Rectangle in Histogram#

LC 85 reduces to LC 84. Make sure you can code LC 84's monotonic stack solution from scratch, explain why the stack stays monotonically increasing, and derive the O(n) time complexity. Without internalising LC 84, LC 85 feels like magic.

LC 221 — Maximal Square#

A gentler variant: instead of the largest rectangle of 1s, find the largest square of 1s. This has a cleaner DP solution without requiring the histogram trick. The recurrence is:

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1   when matrix[i][j] == '1'

The answer is max(dp[i][j])^2. Comparing LC 221 and LC 85 in an interview shows architectural thinking: knowing when a simpler DP suffices vs. when you need a more powerful sub-routine.

3D Extension#

What if the matrix were 3D — a rectangular cuboid of 0s and 1s — and you needed the largest rectangular cuboid of all 1s? The histogram trick generalises: fix one axis, collapse the other two into a 2D Maximal Rectangle problem. You would loop over all "slices" along the fixed axis and apply LC 85 on each cross-section, giving O(m × n × p) for an m × n × p cuboid. This kind of dimensional-extension reasoning is common in system design interviews.

Follow-up: Can you handle a streaming matrix?#

If rows arrive one at a time and you must output the current answer after each row, LC 85's algorithm already handles this — the heights array is updated incrementally. Each new row costs O(n) time. This is exactly the streaming-friendly variant, and the answer is that the existing solution works without modification.

This Pattern Solves#

The "accumulate column heights, then run a 1D algorithm" pattern appears across many hard problems:

• Count submatrices with all 1s — use the same histogram accumulation and count rectangles with a stack in O(n) per row.
• Maximal rectangle in a grid with obstacles — treat obstacles as 0s; the histogram naturally resets.
• Largest rectangle under a skyline — LC 84 directly; no matrix wrapping needed.
• Maximum area rectangle in a histogram with constraints (e.g., width or aspect ratio limits) — extend the histogram algorithm with an additional constraint check during the pop phase.

Any time you encounter a 2D grid problem where "height of consecutive 1s above" is a useful quantity, think about whether LC 84's monotonic stack can be applied per row.

Key Takeaways#

• LC 85 reduces directly to LC 84: accumulate column heights row-by-row, then run the Largest Rectangle in Histogram algorithm on each row's heights array.
• The heights[j] DP transition is: heights[j] += 1 if matrix[row][j] == '1', else reset to 0 — this builds the histogram incrementally in O(n) per row.
• The monotonic stack sub-routine runs in O(n) per row; overall time complexity is O(m * n) where m is rows and n is columns.
• Space complexity is O(n) — only the heights array and stack are needed, not the full matrix copy.
• Streaming variant: if rows arrive one at a time, the same solution works without modification — just update heights and run the stack each time.
• Always handle the '0' reset correctly: the height must become 0, not remain from a previous row, otherwise rectangles spanning rows with a 0 in the middle are counted incorrectly.
• This problem tests the ability to recognize problem reductions — a skill Amazon and Microsoft explicitly value in engineering interviews.