Question

citation: lintcode
Given a 2D boolean matrix. Compute the largest rectangles formed by true values.

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]
]
return 6.

Idea

I didn't invent this. I had no clue how the original author come up with this solution. So basically, you calculate a height for each position in the matrix. You aim to calculate the largest area from left to right. How? You can only do so if all the heights are increasing from left to right.

Given a fixed right position, each height on its left side guarantees to form a rectangle with it IF ONLY IF all the left bars are aligned at increasing order from left to right.

However, the heights are not guaranteed to increase. You have to maintain a stack which accepts only larger heights. When a decreased height at position i is encountered, pop out heights until ith height is no less than stack top.

When you pop out heights, you can start calculating the spanned area from the inclusive poped position to the exclusive ith position. Because ith position is exclusive, you have to add an extra column so that the last column and also be included in the calculation.

An easier version of this question is at here

import java.util.Stack;

public class Solution {
    public int maximalRectangle(boolean[][] matrix) {

        if (matrix.length == 0) return 0;

        int rowLen = matrix.length;
        int colLen = matrix[0].length;

        /**
         * why col plus one? we want to calculate the "spanned" area
         * the extra 1 unit serves as the border, which defaults to zero in Java
         */
        int [][] heights = new int[rowLen][colLen + 1];

        for(int row = 0; row < rowLen; row++) {
            for(int col = 0; col < colLen; col++) {
                if (!matrix[row][col]) {
                    heights[row][col] = 0;
                    continue;
                }
                if (row == 0) {
                    heights[row][col] = 1;
                    continue;
                }
                int previousRowHeight = heights[row - 1][col];
                heights[row][col] = previousRowHeight + 1;
            }
        }

        return maxRecArea(matrix, heights);
    }

    private int maxRecArea(boolean[][] matrix, int[][] heights) {
        int rowLen = matrix.length;
        int area = 0;
        for(int row = 0; row < rowLen; row++) {
            area = Math.max(area, maxRecAreaInRow(heights[row]));
        }
        return area;
    }

    private int maxRecAreaInRow(int[] heightsInRow) {
        Stack<Integer> ascendHeightsIndexes = new Stack<>();

        int col = 0;
        int max = 0;

        // remember, it has one more column than original matrix, which is all zero
        while (col < heightsInRow.length) {

            if (ascendHeightsIndexes.isEmpty()) {
                ascendHeightsIndexes.push(col++);
                continue;
            }

            int previousHeight = heightsInRow[ascendHeightsIndexes.peek()];
            int currentHeight = heightsInRow[col];

            if (previousHeight <= currentHeight) {
                // merge
                ascendHeightsIndexes.push(col);
                col++;
                continue;
            }

            max = findMax(max, ascendHeightsIndexes, heightsInRow, col);
        }

        return max;
    }

    private int findMax(int max, Stack<Integer> ascendHeightsIndexes, int[] heightsInRow, int col) {
        int height = heightsInRow[ascendHeightsIndexes.pop()];
        /**
         * why minus peek minus one?
         * FORMULA: number of spanned units = exclusive end Index - exclusive start Index - 1
         */
        int spannedWidth = (ascendHeightsIndexes.isEmpty()
                ? col
                : col - ascendHeightsIndexes.peek() - 1);
        max = Math.max(max, height * spannedWidth);
        return max;
    }
}