Maximal Rectangle | Leetcode

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

---

Solution: This is a very tricky one. You have to reuse the Largest Rectangle in Histogram algorithm in its entirety as part of the answer. This means that you have to be able to solve that problem before you can solve this one.

Build a matrix of histogram heights, where each row of the matrix can be treated as an independent histogram of heights. What is the "height" here? It is the number of contiguous 1's starting from this cell and going up all the way. For example:

Input:     Heights:
0 1 1 0    0 1 1 0
0 0 1 1    0 0 2 1
1 0 1 1    0 0 3 2

Apply the Largest Rectangle in Histogram algorithm on each row of the heights histogram. Then return the maximum area ever found.

Note: It should not matter whether you calculate the heights going upwards or going downwards.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        
        // Build matrix of heights of ones.
        int[][] heights = new int[matrix.length][matrix[0].length];
        for (int y = 0; y < matrix.length; y++) {
            for (int x = 0; x < matrix[0].length; x++) {
                int height = (matrix[y][x] == '1') ? 1 : 0;
                if (y > 0 && height > 0) height += heights[y - 1][x];
                heights[y][x] = height;
            }
        }
        
        // Use the largest rectangle in histogram algorithm on each row.
        Stack stack = new Stack<>();
        int maxArea = 0;
        for (int y = 0; y < matrix.length; y++) {
            stack.clear();
            maxArea = Math.max(findMaxArea(stack, heights[y]), maxArea);
        }
        return maxArea;
    }
    
    private int findMaxArea(Stack stack, int[] heights) {
        int maxArea = 0;
        int i = 0;
        do {
            while (!stack.isEmpty() && (i == heights.length || heights[i] < heights[stack.peek()])) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(height * width, maxArea);
            }
            stack.push(i++);
        } while (i <= heights.length);
        return maxArea;
    }
}