Maximal Rectangle - Lintcode

Given a 2Dbooleanmatrix filled withFalseandTrue, find the largest rectangle containing allTrueand return its area.

Example

Given a matrix:

[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]

return6.

Analysis

If the array was the following, then it's like the largest rectangle in histogram problem because it can map to 1d array [0, 0, 3, 3, 5]

[0, 0, 0, 0, 1],
[0, 0, 0, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1]

Therefore, we use a 2d array to store the height of the histogram for each row in the matrix

for (int j = 0; j < matrix[0].length; j++) {
    for (int i = 0; i < matrix.length; i++) {
        if (matrix[i][j]) {
            if (i == 0) {
                heights[i][j] = 1;
            } else {
                heights[i][j] = heights[i - 1][j] + 1;
            }
        }
    }
}

The rest is exactly as finding the maximum area in histogram.

Solution

public int maximalRectangle(boolean[][] matrix) {
    int[][] heights = new int[matrix.length][matrix[0].length];

    for (int j = 0; j < matrix[0].length; j++) {
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][j]) {
                if (i == 0) {
                    heights[i][j] = 1;
                } else {
                    heights[i][j] = heights[i - 1][j] + 1;
                }
            }
        }
    }

    int maxArea = 0;
    for (int i = 0; i < matrix.length; i++) {
        maxArea = Math.max(maxArea, helper(heights, i));
    }

    return maxArea;
}

public int helper(int[][] heights, int row) {
    int area = 0;

    Stack<Integer> stack = new Stack<Integer>();

    for (int j = 0; j <= heights[0].length; j++) {
        int curr = 0;
        if (j == heights[0].length) {
            curr = -1;
        } else {
            curr = heights[row][j];
        }

        while (!stack.isEmpty() && heights[row][stack.peek()] > curr) {
            int h = heights[row][stack.pop()];
            int w = stack.isEmpty() ? j : j - stack.peek() - 1;
            area = Math.max(area, h * w);
        }

        stack.push(j);
    }

    return area;
}