Leetcode–Maximal Rectangle

The Problem:

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

Notes:

  1. A DP problem, think of handle each row/column first, get the max length for that row/column, and store it in a 2d array.
  2. Another thing worth mentioning is in the second round, for each non-zero grid should consider a new sequence start from this index since the minrow will change.

Java Solution

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0 || matrix[0].length==0)return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] area = new int[n][m];
        for(int j = 0; j <m; j++){
            area[0][j] = matrix[0][j]=='0'?0:1;
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j]=='0'){
                    area[i][j]=0;
                }
                else{
                    area[i][j] = area[i-1][j]+1;
                }
            }
        }
        int maxarea = 0;
        int minrow;
        for(int i = 0; i < n; i++){
            for(int j=0; j<m;j++){
                if(area[i][j]!=0){
                    minrow= area[i][j];
                    maxarea = Math.max(maxarea,area[i][j]);
                    // from each nonzero grid, start a new try, because min can change
                    for(int k = j+1; k < m; k++){
                        if(area[i][k]==0)
                            break;
                        minrow = Math.min(area[i][k], minrow);
                        maxarea = Math.max(maxarea, minrow * (k-j+1));
                    }
                }
            }
        }
        return maxarea;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s