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;
    }
}

84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Solution:

The idea is for each value at index i, we look left and look right to find the first value smaller than itself.

If we find these two indices, we can calculate the maximum rectangle at this index value height.

We use an increasing stack to store the first left index.

If we find a value is smaller than the top of the stack, this value is the first smaller value from stack top's right.

Therefore, we have stack top's first smaller value from its left and right, thus we can calculate the maximum rectangle with stack top's height.

We also push a dummy index with value -1 after traverse the input, in order to pop out all remaining indices from the stack.

The time complexity is O(n) and the space complexity is O(n).



Code:

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        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;
    }
}