221. Maximal Square

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Solution:

Dynamic programming.
1  1  1
1  1  1
1  1  1
Define dp[i][j] as the maximum square length that the right bottom corner of the square is right on position i, j, so for a 3 X 3 square, dp[0][0] = 1 , dp[1][1]=2, dp[1][2] =2 , dp[2][1]=2, Obviously, dp[1][2] tells us that matrix[0][1] matrix[0][2] matrix[1][1] matrix[1][2] are '1's, similar with dp[1][1] and dp[2][1] we can safely say the whole matrix is filled with '1'. so dp[2][2] should be 3. 
The dp array for it should be
1  1  1
1  2  2
1  2  3
So dp[i][j]= Math. min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
While we update dp we can get the global maximum of the square. 
I am using another variable to update dp[i-1][j-1] so that I can use a one dimensional array to track the dp.

  public int maximalSquare(char[][] matrix) {  
    if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;  
    int m=matrix.length;  
    int n=matrix[0].length;  
     int res=0;  
     int[] dp=new int[n];  
     int pre=0;  
     for(int i=0;i<m;i++){  
       for(int j=0;j<n;j++){  
         if(matrix[i][j]=='0') dp[j]=0;  
         else{  
           int left=j==0? 0: dp[j-1];  
           int up=dp[j];  
           dp[j]=Math.min(Math.min(up,left),pre)+1;  
           pre=up;  
           res=Math.max(res,dp[j]);  
         }  
       }  
     }  
     return res*res;  
   }