MANG Problem #25: Maximal Rectangle (Hard)

1. Problem Statement

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.

Input:

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

Output: 6

2. Approach: Matrix-to-Histogram Reduction

Finding a rectangle in a matrix is hard. Finding the largest rectangle in a Histogram is much easier ($O(N)$).

Iterate through rows: For every row, we treat it as the "base" of a histogram.
Maintain Heights:
- If matrix[r][c] == '1', then heights[c] = heights[c] + 1.
- If matrix[r][c] == '0', then heights[c] = 0 (The base is broken).
Solve Histogram: After building the heights for the current row, calculate the "Largest Rectangle in Histogram" for those heights using a Monotonic Stack.
Global Max: Keep track of the maximum area across all rows.

3. Java Implementation

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int cols = matrix[0].length;
    int[] heights = new int[cols];
    int maxArea = 0;

    for (int r = 0; r < matrix.length; r++) {
        for (int c = 0; c < cols; c++) {
            // Update heights for current row base
            if (matrix[r][c] == '1') heights[c]++;
            else heights[c] = 0;
        }
        maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
    }
    return maxArea;
}

private int largestRectangleInHistogram(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int max = 0;
    for (int i = 0; i < heights.length; i++) {
        while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
            int h = heights[stack.pop()];
            int w = i - stack.peek() - 1;
            max = Math.max(max, h * w);
        }
        stack.push(i);
    }
    while (stack.peek() != -1) {
        int h = heights[stack.pop()];
        int w = heights.length - stack.peek() - 1;
        max = Math.max(max, h * w);
    }
    return max;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: A rectangle in a grid is just a histogram that "continues" across multiple rows. By tracking the heights of 1s in each column, we convert the 2D problem into $M$ 1D problems.
The Histogram Switch: Why heights[c] = 0? Because a rectangle must be contiguous 1s. If there is a '0' in the current row, no rectangle can use the 1s above it for the current base row.
The Optimization: We don't re-calculate everything for every row. We reuse the heights array from the previous row, only updating it for the current row.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(M * N) where M is rows and N is columns. For each of the M rows, we perform an O(N) histogram calculation."
Interviewer: "What if the matrix was sparse?"
You: "If the matrix is mostly 0s, we could optimize by only processing the columns that contain 1s using a sparse representation, but the M*N bound would still hold for the worst case."