#85 Maximal Rectangle - Solution

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.

Example 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
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

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

Example 3:

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

Constraints:

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

The key idea behind solving Maximal Rectangle is to transform each row of the matrix into a histogram. As you iterate through the rows, maintain an array heights where each value represents the number of consecutive 1s ending at the current row for that column. This converts the problem into repeatedly solving the Largest Rectangle in Histogram problem.

For every row, update the histogram heights and then use a monotonic increasing stack to compute the largest rectangle in that histogram efficiently. The stack helps determine the nearest smaller bars to the left and right, allowing you to calculate the maximum area formed by each bar.

This approach combines dynamic programming (to build heights row by row) with a stack-based optimization for histogram processing. Since each cell is processed once and each histogram calculation is linear, the overall time complexity remains efficient.

Approach	Time Complexity	Space Complexity
Brute Force Rectangle Expansion	O(m^2 * n)	O(1)
Histogram + Monotonic Stack	O(m * n)	O(n)

Solutions (5)

Approach Using Histograms and Stack

This approach is inspired by transforming the binary matrix row by row into histograms. For each row, consider it as the base and calculate the height of '1's found upwards in each column (until a '0' is encountered, resetting the height). Using these heights, treat each row as a histogram problem where you need to find the largest rectangular area. You can apply the 'Largest Rectangle in Histogram' algorithm using a stack for efficient processing.

Time Complexity: O(n * m) where n is the number of rows and m is the number of columns.
Space Complexity: O(m), used by the 'heights' array and stack.

Python JavaScript Java

1public int maximalRectangle(char[][] matrix) {
2    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
3    int maxArea = 0;
4    int[] heights = new int[matrix[0].length + 1];
5
6    for (char[] row : matrix) {
7        for (int i = 0; i < matrix[0].length; i++) {
8            if (row[i] == '1') {
9                heights[i]++;
10            } else {
11                heights[i] = 0;
12            }
13        }
14
15        Stack<Integer> stack = new Stack<>();
16        stack.push(-1);
17        for (int i = 0; i < heights.length; i++) {
18            while (heights[i] < heights[stack.peek()]) {
19                int h = heights[stack.pop()];
20                int w = i - 1 - stack.peek();
21                maxArea = Math.max(maxArea, h * w);
22            }
23            stack.push(i);
24        }
25    }
26
27    return maxArea;
28}

Explanation

This Java solution utilizes a similar method as other languages. Heights are computed and stored for each column for each row iteration, addressing maximal rectangle calculation through stack manipulation.

Dynamic Programming Approach

This approach involves using dynamic programming (DP) to compute not only the heights but also left and right boundaries for each row's histogram. By maintaining arrays for each row, you can determine the maximum potential width of a rectangle starting from each point and thereby compute the largest rectangle area efficiently.

Time Complexity: O(n * m) because each cell is processed in constant time.
Space Complexity: O(m), due to extra arrays for heights, and boundaries.

C++C#

1public int MaximalRectangle(char[][] matrix) {
2    if (matrix.Length == 0 || matrix[0].Length == 0) return 0;
3    int maxArea = 0;
4    int[] height = new int[matrix[0].Length];
5    int[] left = new int[matrix[0].Length];
    int[] right = new int[matrix[0].Length];
    Array.Fill(right, matrix[0].Length);

    for (int i = 0; i < matrix.Length; i++) {
        int currentLeft = 0, currentRight = matrix[0].Length;

        for (int j = 0; j < matrix[i].Length; j++) {
            if (matrix[i][j] == '1') height[j]++;
            else height[j] = 0;
        }

        for (int j = 0; j < matrix[i].Length; j++) {
            if (matrix[i][j] == '1') left[j] = Math.Max(left[j], currentLeft);
            else { left[j] = 0; currentLeft = j + 1; }
        }

        for (int j = matrix[i].Length - 1; j >= 0; j--) {
            if (matrix[i][j] == '1') right[j] = Math.Min(right[j], currentRight);
            else { right[j] = matrix[i].Length; currentRight = j; }
        }

        for (int j = 0; j < matrix[i].Length; j++) {
            maxArea = Math.Max(maxArea, height[j] * (right[j] - left[j]));
        }
    }

    return maxArea;
}