Maximal Rectangle [largest rectangle in histogram for each row]

XXX. Maximal Rectangle

Dynamic Programming

Stack

Problem Statement:

Given a binary matrix filled with 0 and 1, find the largest rectangle containing only 1s and return its area.

Algorithm:

The problem extends the "Largest Rectangle in Histogram" algorithm to a 2D binary matrix:

1. Treat each row of the matrix as the base of a histogram. For each cell in the row:
   • If the cell contains 1, increment the histogram height at that column.
   • If the cell contains 0, reset the histogram height at that column to 0.
2. After building the histogram for each row, calculate the largest rectangle area in that histogram using a stack-based algorithm.
3. Track the maximum rectangle area across all rows.

Complexity:

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is processed once, and the stack operations are linear in total.
Space Complexity: O(n), for the histogram and stack used in the algorithm.

Java Implementation:

class Solution {
    // Main function to compute maximal rectangle
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;

        int[] histogram = new int[matrix[0].length]; // Histogram heights
        int max = 0;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                // Update histogram: increment or reset to 0
                if (matrix[i][j] == '1') histogram[j] += 1;
                else histogram[j] = 0;
            }

            // Compute max area in current histogram
            max = Math.max(max, maxRectHisto(histogram));
        }

        return max;
    }

    // Helper function to compute the largest rectangle in a histogram
    public int maxRectHisto(int[] heights) {
        Stack stack = new Stack<>();
        stack.push(-1); // Initialize with a sentinel value

        int max = 0, area = 0, i = 0;

        // Traverse the histogram
        for (i = 0; i < heights.length;) {
            if (stack.peek() == -1 || heights[i] >= heights[stack.peek()]) {
                stack.push(i++); // Push current index if height is increasing
            } else {
                int top = stack.pop(); // Compute area with popped height as smallest bar
                area = heights[top] * (i - stack.peek() - 1);
                max = Math.max(area, max);
            }
        }

        // Process remaining bars in stack
        while (stack.peek() != -1) {
            int top = stack.pop();
            area = heights[top] * (i - stack.peek() - 1);
            max = Math.max(area, max);
        }

        return max;
    }
}

Explanation:

The solution builds on the "Largest Rectangle in Histogram" algorithm by treating each row of the matrix as the base of a histogram:

• Histogram Construction: The heights of the histogram are updated row by row. Heights increase for consecutive 1s and reset to 0 for 0s.
• Largest Rectangle Calculation: For each histogram, a stack-based approach is used to calculate the largest rectangle area efficiently.
• Global Maximum: The maximum area across all histograms is tracked and returned as the result.