Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

85. Maximal Rectangle - Leetcode Solution

Code Implementation

class Solution:
    def maximalRectangle(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        max_area = 0
        n = len(matrix[0])
        heights = [0] * (n + 1)  # Add a dummy zero at the end
        for row in matrix:
            for i in range(n):
                if row[i] == '1':
                    heights[i] += 1
                else:
                    heights[i] = 0
            stack = [-1]
            for i in range(n + 1):
                while heights[i] < heights[stack[-1]]:
                    h = heights[stack.pop()]
                    w = i - stack[-1] - 1
                    max_area = max(max_area, h * w)
                stack.append(i)
        return max_area
      
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int maxArea = 0, n = matrix[0].size();
        vector<int> heights(n + 1, 0); // Add a dummy zero at the end
        for (const auto& row : matrix) {
            for (int i = 0; i < n; ++i) {
                heights[i] = (row[i] == '1') ? heights[i] + 1 : 0;
            }
            stack<int> stk;
            stk.push(-1);
            for (int i = 0; i <= n; ++i) {
                while (stk.top() != -1 && heights[i] < heights[stk.top()]) {
                    int h = heights[stk.top()]; stk.pop();
                    int w = i - stk.top() - 1;
                    maxArea = max(maxArea, h * w);
                }
                stk.push(i);
            }
        }
        return maxArea;
    }
};
      
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int maxArea = 0;
        int n = matrix[0].length;
        int[] heights = new int[n + 1]; // Add a dummy zero at the end
        for (char[] row : matrix) {
            for (int i = 0; i < n; i++) {
                if (row[i] == '1') heights[i]++;
                else heights[i] = 0;
            }
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            for (int i = 0; i <= n; i++) {
                while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
                    int h = heights[stack.pop()];
                    int w = i - stack.peek() - 1;
                    maxArea = Math.max(maxArea, h * w);
                }
                stack.push(i);
            }
        }
        return maxArea;
    }
}
      
var maximalRectangle = function(matrix) {
    if (!matrix.length || !matrix[0].length) return 0;
    let maxArea = 0, n = matrix[0].length;
    let heights = new Array(n + 1).fill(0); // Add a dummy zero at the end
    for (let row of matrix) {
        for (let i = 0; i < n; i++) {
            heights[i] = row[i] === '1' ? heights[i] + 1 : 0;
        }
        let stack = [-1];
        for (let i = 0; i <= n; i++) {
            while (heights[i] < heights[stack[stack.length - 1]]) {
                let h = heights[stack.pop()];
                let w = i - stack[stack.length - 1] - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
    }
    return maxArea;
};

Problem Description

Given a 2D binary matrix matrix filled with '0's and '1's, find the largest rectangle containing only '1's and return its area. Each cell in matrix can only be used once, and rectangles must be made up of consecutive rows and columns. The rectangle must be entirely filled with '1's, and you must return the area (the number of cells) of the largest such rectangle. There is only one valid area for the largest rectangle.

Thought Process

At first glance, this problem seems similar to finding the largest rectangle in a histogram, but in two dimensions. The brute-force approach would be to check every possible rectangle in the matrix and count the number of '1's, but this is very inefficient for large matrices. Instead, we can notice that for each row, if we treat the row as the base of a histogram (where each column's height is the number of consecutive '1's above), we can use the efficient "Largest Rectangle in Histogram" algorithm for each row. This reduces the 2D problem to a series of 1D problems, one for each row.

Solution Approach

The optimized solution works by transforming each row into a histogram and then using a stack-based algorithm to compute the largest rectangle for that histogram. Here are the steps:
  1. For each row, maintain an array heights where heights[i] is the number of consecutive '1's in column i up to the current row.
  2. For each row, update heights by incrementing for '1's and resetting to zero for '0's.
  3. For each updated heights array (i.e., for each row), apply the "Largest Rectangle in Histogram" algorithm:
    • Use a stack to keep track of indices with increasing heights.
    • When a smaller height is found, pop from the stack and calculate the area with the popped height as the smallest bar.
    • Continue this for the entire row, and update the maximal area found so far.
  4. After processing all rows, return the maximal area found.
We use a stack because it allows us to efficiently compute the largest rectangle for each histogram in linear time per row.

Example Walkthrough

Suppose matrix is: 
[
  ['1','0','1','0','0'],
  ['1','0','1','1','1'],
  ['1','1','1','1','1'],
  ['1','0','0','1','0']
]
Let's walk through each row:
  • Row 0: heights = [1,0,1,0,0] → Largest rectangle is 1.
  • Row 1: heights = [2,0,2,1,1] → Largest rectangle is 3 (at columns 2,3,4).
  • Row 2: heights = [3,1,3,2,2] → Largest rectangle is 6 (columns 0,2,3,4, height 2).
  • Row 3: heights = [4,0,0,3,0] → Largest rectangle is 4 (column 0, height 4).
The largest area found is 6.

Time and Space Complexity

  • Brute-force: For every possible rectangle, check all cells inside it. There are O(m2n2) rectangles in an m x n matrix, making the time complexity O(m3n3).
  • Optimized (stack-based): For each row, we process the heights in O(n) time (using the histogram algorithm). For m rows, total time is O(mn).
  • Space complexity: We use O(n) extra space for the heights and stack arrays.

Summary

The key insight is to treat each row as the base of a histogram, enabling us to use an efficient stack-based algorithm for the largest rectangle in a histogram. By updating heights as we process each row and applying the histogram technique, we reduce a 2D problem to a sequence of 1D problems, achieving an O(mn) solution. This approach is both elegant and efficient, leveraging classic algorithmic techniques to solve a seemingly complex problem.