Maximal Rectangle

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

Analysis

Height counts the number of successive '1's above (plus the current one). The value of left & right means the boundaries of the rectangle which contains the current point with a height of value height.

Code

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix==null || matrix.length==0 || matrix[0].length==0) {return 0;}

        int m = matrix.length;
        int n = matrix[0].length;

        int[] left = new int[n];
        int[] right = new int[n];
        int[] height = new int[n];
        Arrays.fill(left, 0);
        Arrays.fill(right, n);
        Arrays.fill(height, 0);

        int max = 0;

        for (int i=0; i<m; i++){
            int curLeft = 0, curRight = n;
            for (int j=0; j<n; j++){
                if (matrix[i][j]=='1') height[j]++;
                else height[j]=0;
            }
            for (int j=0; j<n; j++){
                if (matrix[i][j]=='1') left[j]=Math.max(left[j], curLeft);
                else {left[j]=0; curLeft=j+1;}
            }
            for(int j=n-1; j>=0; j--) {
                if(matrix[i][j]=='1') right[j]=Math.min(right[j],curRight);
                else {right[j]=n; curRight=j;}    
            }
            for(int j=0; j<n; j++)
                max = Math.max(max,(right[j]-left[j])*height[j]);
        }


        return max;
    }
}

Note

• Need more thinking!

Reference

Leetcode