85. Maximal Rectangle

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.



Solution:

This problem can be split to the sub problems:

1. calculate the largest rectangle histogram of row 1.

2. calculate the largest rectangle histogram of row 1 and row 2 together.

3. calculate the largest rectangle histogram of row 1, 2, and 3 together.

...


n. calculate the largest rectangle histogram of row 1, 2, to n together.

Take the max of the above largest rectangle histograms.

We know Largest Rectangle in Histogram can be done with O(n) time and O(n) space.

Therefore, this problem can be done in O(mn) time with O(n) space.



Code:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                heights[j] = i == 0 ? matrix[i][j] - '0' : matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            max = Math.max(max, findMaxHistogram(heights));
        }
        return max;
    }
    
    public int findMaxHistogram(int[] heights) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= heights.length; i++) {
            int curr = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && curr <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }
        return max;
    }
}