LeetCode: Maximal Rectangle

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.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(matrix.length==0) return 0;
        int m = matrix.length, 
            n = matrix[0].length;
        int[][] leftBounds = new int[m][n], 
                rightBounds = new int[m][n]; 
        int[]   toleft = new int[n],
                toright = new int[n],
                heights = new int[n];
        
        countBoundaries(matrix,leftBounds,rightBounds);
        
        int max = 0;        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(i>0&&matrix[i-1][j]=='1'){
                        heights[j]=heights[j]+1;
                        toleft[j]=Math.max(leftBounds[i][j],toleft[j]);
                        toright[j]= Math.min(rightBounds[i][j],toright[j]);
                    }else{
                        heights[j]=1;
                        toleft[j]=leftBounds[i][j];
                        toright[j]=rightBounds[i][j];
                    }
                    max=Math.max(max,heights[j]*(toright[j]-toleft[j]+1));
                }
            }
        }
        return max;
    }
    
    public void countBoundaries(char[][] matrix, int [][]left, int [][]right){
        int m = matrix.length, 
            n = matrix[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                if(matrix[i][j]=='1'){
                    left[i][j]=j>0&&matrix[i][j-1]=='1'?left[i][j-1]:j;
                }
        }
        
        for(int i=0;i<m;i++){
            for(int j=n-1;j>=0;j--){
                if(matrix[i][j]=='1'){
                    right[i][j]=j<n-1&&matrix[i][j+1]=='1'?right[i][j+1]:j;
                }
            }
        }
    }
}