Maximum Rectangle

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

First of all, this is not the most optimal solution. In fact, the code below only passes 87% of the test cases. But this is my original solution.

Take each matrix position as the left corner, and then try to extend its row length and column length to form a rectangle. If success, update the computed max area.

Code

public class Solution {
    /*
     * @param matrix: a boolean 2D matrix
     * @return: an integer
     */
    public int maximalRectangle(boolean[][] matrix) {
        // write your code here
        if (matrix.length == 0) return 0;

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

        int area = 0;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if (!matrix[i][j]) continue;
                area = Math.max(area, findMax(matrix, i, j));
            }
        }
        return area;
    }

    private int findMax(boolean[][] matrix, int i, int j) {
        int step = 0;
        return findMax(matrix, i, j, i, j, step, step);
    }

    private int findMax(boolean[][] matrix,
                        int row, int col,
                        int oldRowEnd, int oldColEnd,
                        int stepsRow, int stepsCol) {

        int rowEnd = oldRowEnd + stepsRow;
        int colEnd = oldColEnd + stepsCol;

        boolean inBound = rowEnd >= 0 && rowEnd < matrix.length &&
                colEnd >= 0 && colEnd < matrix[0].length;

        if (!inBound) return 0;

        for(int extendRow = oldRowEnd + 1; extendRow <= rowEnd; extendRow++) {
            for (int c = col; c <= colEnd; c++) {
                if (!matrix[extendRow][c]) {
                    return 0;
                }
            }
        }

        for(int extendCol = oldColEnd + 1; extendCol <= colEnd; extendCol++) {
            for (int r = row; r <= rowEnd; r++) {
                if (!matrix[r][extendCol]) {
                    return 0;
                }
            }
        }

        int area = (rowEnd - row + 1) * (colEnd - col + 1);
        area = Math.max(area, findMax(matrix, row, col, rowEnd, colEnd, 0, 1));
        area = Math.max(area, findMax(matrix, row, col, rowEnd, colEnd, 1, 0));
        return area;
    }
}