Leetcode 85. Maximal Rectangle

 85. Maximal Rectangle

Hard, Dynamic Programming

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'

To solve the Maximal Rectangle problem, we can use a combination of dynamic programming and a monotonic stack approach, which is efficient and works in $O(m \times n)$ time complexity, where m is the number of rows and n is the number of columns.

Approach:

1. Transform the problem into a histogram problem:

   • For each row, consider it as the base of a histogram where the heights of the bars are calculated by counting consecutive 1s vertically in the matrix. Essentially, the height of a bar at column j for row i is the number of consecutive 1s ending at that cell.
   • For every row, we will compute the histogram heights and then find the largest rectangle area that can be formed with those heights using a monotonic stack approach.

2. For each row:

   • Update the histogram of heights.
   • Calculate the maximal rectangle area for the updated histogram using a stack.

3. Use a monotonic stack to find the largest rectangle in the histogram:

   • For a given histogram, maintain a stack of column indices in increasing order of their heights. This allows us to efficiently calculate the largest rectangle area at each step.

Code:

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }

        int m = matrix.Length;
        int n = matrix[0].Length;
        int[] heights = new int[n];
        int maxArea = 0;

        // Iterate through each row of the matrix
        for (int i = 0; i < m; i++) {
            // Update the heights array based on the current row
            for (int j = 0; j < n; j++) {
                // If the current cell is '1', increase the height; otherwise, reset to 0
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }

            // Calculate the maximum area for the current histogram (heights array)
            maxArea = Math.Max(maxArea, MaxHistogramArea(heights));
        }

        return maxArea;
    }

    private int MaxHistogramArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int n = heights.Length;

        // Iterate through the heights array and process each bar in the histogram
        for (int i = 0; i <= n; i++) {
            // While there are bars in the stack and the current bar is shorter than the top bar in the stack
            while (stack.Count > 0 && (i == n || heights[stack.Peek()] > heights[i])) {
                int h = heights[stack.Pop()];  // Get the height of the bar
                int width = stack.Count > 0 ? i - stack.Peek() - 1 : i;  // Calculate the width
                maxArea = Math.Max(maxArea, h * width);  // Update the maximum area
            }
            stack.Push(i);  // Push the current index onto the stack
        }

        return maxArea;
    }
}

Explanation:

1. Updating the histogram (heights array):

   • For each row, we traverse all columns. If the value is 1, we increase the corresponding value in the heights array. If the value is 0, we reset the corresponding height to 0 because the rectangle cannot extend further down.

2. Monotonic stack approach (MaxHistogramArea):

   • The function MaxHistogramArea calculates the largest rectangle area that can be formed from the histogram represented by the heights array.
   • We use a stack to store column indices in increasing order of their heights. For each column, if the current height is smaller than the height of the column at the top of the stack, we pop the stack and calculate the area of the rectangle formed with the popped height. The width of the rectangle is determined by the difference between the current index and the index of the new top of the stack.
   • This ensures that we can calculate the largest rectangle area in linear time $O(n)$ for each row.

3. Final Result:

   • For each row, after updating the heights array, we calculate the maximum rectangle area using the MaxHistogramArea function and update the global maxArea.

Time Complexity:

• Time Complexity: $O(m \times n)$, where m is the number of rows and n is the number of columns. We process each element in the matrix once and calculate the maximal rectangle for each histogram in linear time $O(n)$.
• Space Complexity: $O(n)$ for the heights array and the stack.

Example Walkthrough:

For the input:

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]

• After processing the first row, the heights array becomes [1, 0, 1, 0, 0].
• After processing the second row, the heights array becomes [2, 0, 2, 1, 1].
• After processing the third row, the heights array becomes [3, 1, 3, 2, 2].
• After processing the fourth row, the heights array becomes [4, 0, 0, 3, 0].

The maximum area found is 6 by considering the rectangle of width 3 and height 2 in the third row.

Edge Cases:

1. If the matrix is empty, the result is 0.
2. If all elements are 0, the result is 0.
3. If the matrix contains only 1s, the area is simply the entire matrix area.
4. The solution handles matrices of varying sizes and row/column distributions efficiently.

This approach is optimal and works well for the given constraints.