Maximal Rectangle hard

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.

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 = [] Output: 0

Steps

The problem can be efficiently solved using a stack-based approach, leveraging the idea from the "Largest Rectangle in Histogram" problem. Here's a breakdown of the steps:

1. Initialization: Create a height array to store the height of the histogram at each column. This height represents the number of consecutive '1's encountered vertically at that column.

2. Iteration: Iterate through the matrix row by row. For each row:

   • Update the height array: If the current cell is '1', increment the corresponding height in the height array. If it's '0', reset the height to 0.
   • Calculate the maximal rectangle area for the current histogram (represented by the height array) using a stack. This is where we adapt the histogram approach.

3. Stack-Based Area Calculation: Use a stack to maintain indices of increasing heights. For each bar (height) in the height array:

   • While the stack is not empty and the current height is less than or equal to the height of the bar at the top of the stack:
     • Pop the top index from the stack.
     • Calculate the area of the rectangle using the popped index, the current index, and the height of the popped bar. Update the maximal area if necessary.
   • Push the current index onto the stack.

4. Handling Remaining Bars: After iterating through the height array, the stack may still contain indices. Process these remaining bars as described in step 3.

5. Return Maximal Area: Return the calculated maximal area.

Explanation

The key idea is to treat each row of the matrix as a histogram. The height of each bar in the histogram represents the number of consecutive '1's vertically in that column. By calculating the maximal rectangle area for each row's histogram using the stack-based approach (similar to the largest rectangle in histogram problem), we find the overall maximal rectangle area. The stack efficiently handles the calculation of areas considering the heights of bars to the left and right of a given bar.

Code

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

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] height = new int[cols];
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                } else {
                    height[j] = 0;
                }
            }
            maxArea = Math.max(maxArea, largestRectangleArea(height));
        }

        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;

        while (i < heights.length) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, area);
            }
        }

        while (!stack.isEmpty()) {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }
}

Complexity

• Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns in the matrix. Each cell is visited once, and the stack operations take at most O(n) time per row.

• Space Complexity: O(n), where 'n' is the number of columns. This is due to the height array and the stack used in largestRectangleArea.