Maximal Rectangle — Hard Problem & Solution

A binary matrix is given as rows of the characters 0 and 1. Find the largest rectangle made entirely of 1s and return its area.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix, Stack, Monotonic Stack
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary matrix is given as rows of the characters 0 and 1. Find the largest rectangle made entirely of 1s and return its area.

Example 1

Input: matrix = ["10100","10111","11111","10010"]
Output: 6
Explanation: The 2 × 3 block of 1s in the middle two rows.

Example 2

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

Example 3

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

Constraints

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

How to solve Maximal Rectangle

Reduce the 2D problem to rows one-dimensional ones. For each row, heights[j] is the number of consecutive 1s ending at that row in column j; the largest all-1s rectangle whose bottom edge is that row is the largest rectangle in that histogram.

Approach

Sweep rows, updating heights[j] to heights[j] + 1 on a 1 and to 0 on a 0.
For each histogram, keep a stack of indices with increasing heights.
When the incoming bar is not taller, pop: the popped bar's rectangle runs from just after the new stack top to just before the current index.
A sentinel bar of height 0 past the end flushes the stack.

Why it works

Every all-1s rectangle has a bottom row, and within that row its height in each column is at most the run ending there — so it is counted by that row's histogram, and no rectangle is missed. The stack works because a bar is popped exactly when its right boundary is found, and its left boundary is the element below it, giving each bar's maximal span in O(1) amortised time.

Complexity

Time — O(rows · cols)
Space — O(cols)

Pitfalls

Resetting heights[j] to 0 on a 0 is what keeps the bars contiguous.
Without the trailing sentinel the bars still on the stack are never measured.
Popping on >= rather than > is safe here: equal bars give the same maximal area when the last of them is popped.

Reference solution

Python

from typing import List

def maximalRectangle(matrix: List[str]) -> int:
    m, n = len(matrix), len(matrix[0])
    heights = [0] * (n + 1)
    best = 0
    for i in range(m):
        for j in range(n):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
        stack = []
        for j in range(n + 1):
            while stack and heights[stack[-1]] >= heights[j]:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                best = max(best, h * (j - left - 1))
            stack.append(j)
    return best

JavaScript

var maximalRectangle = function(matrix) {
    var m = matrix.length, n = matrix[0].length, i, j;
    var heights = [];
    for (j = 0; j <= n; j++) heights.push(0);
    var best = 0;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) heights[j] = matrix[i].charAt(j) === "1" ? heights[j] + 1 : 0;
        var stack = [];
        for (j = 0; j <= n; j++) {
            while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[j]) {
                var h = heights[stack.pop()];
                var left = stack.length > 0 ? stack[stack.length - 1] : -1;
                var area = h * (j - left - 1);
                if (area > best) best = area;
            }
            stack.push(j);
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue