Maximal Rectangle — Applying Histogram Analysis Row by Row

Problem Statement#

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

Constraints:

• rows == matrix.length
• cols == matrix[0].length
• 1 <= rows, cols <= 200
• matrix[i][j] is '0' or '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

Input:  matrix = [["0"]]
Output: 0

Why This Problem Matters#

Maximal Rectangle is one of the top hardest problems on LeetCode and a frequently asked senior onsite question at Google and Meta. It teaches a critical algorithmic skill: problem reduction. Instead of solving the 2D problem directly (which would require a complex 2D algorithm), you reduce it to a sequence of 1D problems — each row becomes a histogram where you apply the known O(n) algorithm.

This reduction pattern appears throughout algorithms: 2D matrix problems reduced to 1D, 3D problems reduced to 2D. In an interview, articulating the reduction clearly before coding is what separates candidates who understand the problem from those who memorized it.

Mastering this problem requires first mastering LC 84 Largest Rectangle in Histogram — this problem is a direct extension.

The Core Insight#

The reduction to histogram: Consider row r as the base of a histogram. For each column c, the bar height is the number of consecutive '1's ending at row r. If matrix[r][c] == '0', the height resets to 0.

Any rectangle of all '1's with its bottom edge on row r corresponds exactly to a rectangle in this histogram. Therefore: for each row, build the height array and apply Largest Rectangle in Histogram. Take the maximum across all rows.

Height array update: For each row r and column c:

• If matrix[r][c] == '1': heights[c] += 1
• If matrix[r][c] == '0': heights[c] = 0

This runs in O(cols) per row, and the histogram algorithm runs in O(cols) per row, giving O(rows * cols) total.

Visual Dry Run#

Matrix:

["1","0","1","0","0"]
["1","0","1","1","1"]
["1","1","1","1","1"]
["1","0","0","1","0"]

Row 2 heights [3,1,3,2,2] give the largest rectangle of area 6 (spanning 3 columns at height 2, or 2 columns at height 3).

Overall maximum: 6.

Solution (Optimal)#

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
 
        cols = len(matrix[0])
        heights = [0] * cols
        max_area = 0
 
        def largest_rect(h: list[int]) -> int:
            h = h + [0]
            stack = [-1]
            area = 0
            for i, val in enumerate(h):
                while stack[-1] != -1 and h[stack[-1]] >= val:
                    height = h[stack.pop()]
                    width = i - stack[-1] - 1
                    area = max(area, height * width)
                stack.append(i)
            return area
 
        for row in matrix:
            for c in range(cols):
                heights[c] = heights[c] + 1 if row[c] == '1' else 0
            max_area = max(max_area, largest_rect(heights))
 
        return max_area

var maximalRectangle = function(matrix) {
    if (!matrix.length || !matrix[0].length) return 0;
 
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;
 
    function largestRect(h) {
        const arr = [...h, 0];
        const stack = [-1];
        let area = 0;
        for (let i = 0; i < arr.length; i++) {
            while (stack[stack.length - 1] !== -1 && arr[stack[stack.length - 1]] >= arr[i]) {
                const height = arr[stack.pop()];
                const width = i - stack[stack.length - 1] - 1;
                area = Math.max(area, height * width);
            }
            stack.push(i);
        }
        return area;
    }
 
    for (const row of matrix) {
        for (let c = 0; c < cols; c++) {
            heights[c] = row[c] === '1' ? heights[c] + 1 : 0;
        }
        maxArea = Math.max(maxArea, largestRect(heights));
    }
 
    return maxArea;
};

Time: O(m * n) — m rows each with an O(n) histogram computation Space: O(n) — height array reused across rows; stack is also O(n)

Common Mistakes#

• Trying to solve it as a 2D DP problem from scratch — this leads to complex O(m²n) solutions; the histogram reduction gives O(mn) cleanly
• Forgetting to reset heights to 0 on '0' cells — bars must not accumulate through '0' cells; this is the most common bug
• Treating matrix cells as integers instead of strings — the problem specifies '0' and '1' as string characters; compare with == '1' not == 1
• Bugs in the histogram subroutine — any error in the sentinel handling or width formula propagates to wrong answers; test the histogram function separately before embedding it
• Making unnecessary copies of the heights array — update it in-place each row to save O(m*n) extra space

Interview Tips#

• State the reduction immediately: "This problem reduces to Largest Rectangle in Histogram. For each row, I build a cumulative height array. Height increases by 1 on '1' cells and resets to 0 on '0' cells. I apply the histogram algorithm on each row."
• Give the geometric intuition: "Any rectangle of all 1s has a bottom row. I fix that bottom row and ask: what is the tallest rectangle whose bottom is exactly this row? The cumulative heights tell me how many consecutive 1s are above each column."
• Code the histogram function first, verify it on [2,1,5,6,2,3], then embed it in the matrix loop.

Follow-up Questions#

• What if the matrix contains integers 0-9 and you want the largest rectangle with all values >= k? Preprocess: treat each cell as 1 if >= k, else 0. Apply the same algorithm.
• Can you solve this without the histogram reduction, using pure DP? Yes: dp[i][j] = width of widest all-1s horizontal run ending at column j in row i. Then for each cell, iterate upward. This is O(m²n) and less efficient.
• What if you want the maximum square of 1s instead of rectangle (LC 221)? Much simpler DP: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == '1'.

Key Takeaways#

• Reduce the 2D rectangle problem to a series of 1D histogram problems — this reduction is the insight that makes the problem solvable efficiently.
• Maintain a cumulative height array: height increases by 1 on '1' cells, resets to 0 on '0' cells.
• Apply the O(n) monotonic stack histogram algorithm (LC 84) on each row's height array.
• The maximum across all rows is the final answer.
• This problem requires LC 84 as a prerequisite — do not attempt LC 85 without fully mastering LC 84 first.
• The height array is reused across rows in O(n) space — avoid unnecessary copying.
• Compare matrix cells with == '1' not == 1 — the input is strings, not integers.