Maximal Rectangle

Published at23 Jul 2026

Stack Hard 2 views

Like0

You are given a 2D binary matrix. Find the area of the largest rectangle containing only 1s.

This builds on the Largest Rectangle in Histogram algorithm. Treat each row as a base: compute heights of consecutive 1s ending at each cell. For each row, apply the histogram algorithm to find the max rectangle for that row. The overall max is the answer. Heights update per row: if cell is 1, add 1; if 0, reset to 0. Then run the monotonic stack histogram algorithm. Time O(n*m).

The key insight is that each row can be treated as a histogram. By applying the histogram algorithm to each row's heights, you find the maximum rectangle ending at that row. The global max across all rows is the answer.

This problem extends the Largest Rectangle in Histogram to two dimensions. The observation is that each row can be treated as a base of a histogram, where the height of each bar is the number of consecutive 1s ending at that cell in the current row. By iterating through the rows and updating the heights, you can apply the histogram algorithm at each row to find the maximum rectangle that ends at that row.

The time complexity is O(rows * cols) because each row runs the linear histogram algorithm. The space complexity is O(cols) for the heights array. This is optimal since you must examine each cell at least once.

To build the heights array, iterate through each row. For each cell, if it contains '1', add 1 to the previous height at that column; if '0', reset the height to 0. Then run the histogram algorithm on the current heights array. The histogram algorithm uses a monotonic increasing stack: when a shorter bar is encountered, it pops taller bars and calculates their area using the current index as right boundary and the new top of stack as left boundary. The overall maximum across all rows is the final answer.

A common optimization is to append a 0 to the heights array before running the histogram algorithm, which forces all remaining bars to be processed without needing special handling after the loop. This simplifies the code and avoids edge cases with the last bar.

Example Input & Output

Example 1

Input

["0"]

Output

Explanation

No 1s.

Example 2

Input

["10100","10111","11111","10010"]

Output

Explanation

Max rectangle area 6.

Example 3

Input

["1"]

Output

Explanation

Single 1.

Algorithm Flow

Recommendation Algorithm Flow for Maximal Rectangle

Solution Approach

Find the largest rectangle containing only 1s in a binary matrix. Treat each row as a histogram base where the height at each column is the number of consecutive 1s up to that row. For each row, update the heights array and compute the largest rectangle in the histogram using a stack. The stack maintains indices of increasing heights, computing area when a smaller height is encountered.

function maximalRectangle(matrix) {
  if (!matrix.length) return 0;
  var heights = Array(matrix[0].length).fill(0), maxArea = 0;
  for (var r = 0; r < matrix.length; r++) {
    for (var c = 0; c < matrix[0].length; c++) {
      heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
    }
    maxArea = Math.max(maxArea, largestRectangle(heights));
  }
  return maxArea;
  function largestRectangle(h) {
    var stack = [], max = 0;
    for (var i = 0; i <= h.length; i++) {
      var cur = i === h.length ? 0 : h[i];
      while (stack.length && cur < h[stack[stack.length - 1]]) {
        var height = h[stack.pop()];
        var width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
        max = Math.max(max, height * width);
      }
      stack.push(i);
    }
    return max;
  }
}

Each row builds on the previous row's heights. When a '0' is encountered, the height resets to 0, breaking the histogram. The largest-rectangle-in-histogram subproblem is solved using a monotonic stack in O(cols) time.

Time complexity is O(rows * cols), space complexity is O(cols).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int solution(String[] matrix) {
        if (matrix.length == 0) return 0;
        int[] h = new int[matrix[0].length()];
        int maxA = 0;
        for (String row : matrix) {
            for (int j = 0; j < row.length(); j++)
                h[j] = row.charAt(j) == '1' ? h[j] + 1 : 0;
            maxA = Math.max(maxA, largest(h));
        }
        return maxA;
    }
    int largest(int[] h) {
        Stack<Integer> s = new Stack<>();
        int m = 0;
        for (int i = 0; i <= h.length; i++) {
            int ch = i < h.length ? h[i] : 0;
            while (!s.isEmpty() && ch < h[s.peek()]) {
                int ht = h[s.pop()];
                int w = s.isEmpty() ? i : i - s.peek() - 1;
                m = Math.max(m, ht * w);
            }
            s.push(i);
        }
        return m;
    }
}

javascript

function solution(matrix) {
  if (!matrix.length) return 0;
  var h = new Array(matrix[0].length).fill(0), maxA = 0;
  for (var i = 0; i < matrix.length; i++) {
    for (var j = 0; j < matrix[0].length; j++)
      h[j] = matrix[i][j] === '1' ? h[j] + 1 : 0;
    maxA = Math.max(maxA, largest(h));
  }
  return maxA;
  function largest(h) {
    var s = [], m = 0;
    for (var k = 0; k <= h.length; k++) {
      var ch = k < h.length ? h[k] : 0;
      while (s.length && ch < h[s[s.length-1]]) {
        var ht = h[s.pop()];
        var w = s.length ? k - s[s.length-1] - 1 : k;
        m = Math.max(m, ht * w);
      }
      s.push(k);
    }
    return m;
  }
}

php

<?php
function solution($matrix) {
    if (empty($matrix)) return 0;
    $h = array_fill(0, strlen($matrix[0]), 0);
    $maxA = 0;
    foreach ($matrix as $row) {
        for ($j = 0; $j < strlen($row); $j++)
            $h[$j] = $row[$j] === '1' ? $h[$j] + 1 : 0;
        $maxA = max($maxA, largest($h));
    }
    return $maxA;
}
function largest($h) {
    $s = []; $m = 0;
    for ($i = 0; $i <= count($h); $i++) {
        $ch = $i < count($h) ? $h[$i] : 0;
        while (!empty($s) && $ch < $h[end($s)]) {
            $ht = $h[array_pop($s)];
            $w = empty($s) ? $i : $i - end($s) - 1;
            $m = max($m, $ht * $w);
        }
        array_push($s, $i);
    }
    return $m;
}

python

def solution(matrix):
    if not matrix: return 0
    h = [0] * len(matrix[0])
    max_area = 0
    for row in matrix:
        for j, ch in enumerate(row):
            h[j] = h[j] + 1 if ch == '1' else 0
        max_area = max(max_area, largest(h))
    return max_area

def largest(h):
    s, m = [], 0
    for i in range(len(h) + 1):
        ch = h[i] if i < len(h) else 0
        while s and ch < h[s[-1]]:
            ht = h[s.pop()]
            w = i - s[-1] - 1 if s else i
            m = max(m, ht * w)
        s.append(i)
    return m

rust

fn solution(matrix: Vec<String>) -> i32 {
    if matrix.is_empty() { return 0; }
    let mut h = vec![0; matrix[0].len()];
    let mut max_a = 0;
    for row in &matrix {
        for (j, ch) in row.chars().enumerate() {
            h[j] = if ch == '1' { h[j] + 1 } else { 0 };
        }
        max_a = max_a.max(largest(&h));
    }
    max_a
}
fn largest(h: &[i32]) -> i32 {
    let mut s: Vec<usize> = Vec::new();
    let mut m = 0;
    for i in 0..=h.len() {
        let ch = if i < h.len() { h[i] } else { 0 };
        while let Some(&top) = s.last() {
            if ch >= h[top] { break; }
            let ht = h[s.pop().unwrap()];
            let w = if s.is_empty() { i as i32 } else { (i - *s.last().unwrap() - 1) as i32 };
            m = m.max(ht * w);
        }
        s.push(i);
    }
    m
}

typescript

function solution(matrix: string[]): number {
    if (!matrix.length) return 0;
    var h: number[] = [];
    for (var j = 0; j < matrix[0].length; j++) h.push(0);
    var maxA = 0;
    for (var i = 0; i < matrix.length; i++) {
        for (var j = 0; j < matrix[0].length; j++)
            h[j] = matrix[i][j] === '1' ? h[j] + 1 : 0;
        maxA = Math.max(maxA, largest(h));
    }
    return maxA;
    function largest(h: number[]): number {
        var s: number[] = [], m = 0;
        for (var k = 0; k <= h.length; k++) {
            var ch = k < h.length ? h[k] : 0;
            while (s.length && ch < h[s[s.length-1] as number]) {
                var ht = h[s.pop() as number];
                var w = s.length ? k - (s[s.length-1] as number) - 1 : k;
                m = Math.max(m, ht * w);
            }
            s.push(k);
        }
        return m;
    }
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Maximal Rectangle

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Maximum Nesting Depth

Simplify Path

Final Prices With Discount

Clear Digits

Crawler Log Folder

Build Array With Stack Operations

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.