Maximal Rectangle

Hard
919.

Maximal Rectangle

Maximal Rectangle is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Microsoft and Indeed interviews.

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'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximal Rectangle — Solution in Python, Java & C++

Maximal Rectangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximal Rectangle is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Microsoft and Indeed interviews.

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'

Hints for Maximal Rectangle

  1. Hint 1

    Treat each row as the ground of a histogram whose bars are the runs of 1s ending at that row.

  2. Hint 2

    Then the answer is the best "largest rectangle in a histogram" over all rows.

  3. Hint 3

    Solve each histogram in linear time with a stack of increasing bar heights.

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

  1. Sweep rows, updating heights[j] to heights[j] + 1 on a 1 and to 0 on a 0.
  2. For each histogram, keep a stack of indices with increasing heights.
  3. 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.
  4. 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

Java

public static int maximalRectangle(String[] matrix) {
    int m = matrix.length, n = matrix[0].length();
    int[] heights = new int[n + 1];
    int[] stack = new int[n + 2];
    int best = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            heights[j] = matrix[i].charAt(j) == '1' ? heights[j] + 1 : 0;
        }
        int top = 0;
        for (int j = 0; j <= n; j++) {
            while (top > 0 && heights[stack[top - 1]] >= heights[j]) {
                int h = heights[stack[--top]];
                int left = top > 0 ? stack[top - 1] : -1;
                best = Math.max(best, h * (j - left - 1));
            }
            stack[top++] = j;
        }
    }
    return best;
}

C++

int maximalRectangle(vector<string>& matrix) {
    int m = (int) matrix.size(), n = (int) matrix[0].size();
    vector<int> heights(n + 1, 0);
    int best = 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;
        }
        vector<int> stack;
        for (int j = 0; j <= n; j++) {
            while (!stack.empty() && heights[stack.back()] >= heights[j]) {
                int h = heights[stack.back()];
                stack.pop_back();
                int left = stack.empty() ? -1 : stack.back();
                best = max(best, h * (j - left - 1));
            }
            stack.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming