My Java solution...


  • 0
    6
    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if (null==matrix || matrix.length==0 || matrix[0].length==0)
                return 0;
            
            int max = 0;
            int[] row = new int[matrix[0].length];
            for (int i=0; i<matrix.length; i++) {
                for (int j=0; j<matrix[0].length; j++) {
                    if (matrix[i][j]=='0')
                        row[j] = 0;
                    else
                        row[j] += 1;
                }
                
                int val = maxInRow(row);
                if (val>max)
                    max = val;
            }
            
            return max;
        }
        
        private int maxInRow(int[] row) {
            int max = 0;
            for (int i=0; i<row.length; i++) {
                int minH = row[i];
                for (int j=i; j<row.length; j++) {
                    if (row[j]==0)
                        break;
                    
                    if (row[j]<minH)
                        minH = row[j];
                    
                    int len = Math.min(minH, (j-i+1));
                    int area = len * len;
                    if (area>max)
                        max = area;
                }
            }
            
            return max;
        }
    }

  • 0
    R

    public class Solution {

    public int maximalSquare(char[][] matrix) {
             int count=0;
    	Boolean current =false;
    	int FinalNum=0;
    	
    	if(matrix.length==0 )
    	{	count=0;
    	  return count;}
    	
    	
    	for(int i=0;i< matrix.length;i++)
    	  for(int j=0; j<matrix[i].length;j++){
    		  
    		   current=true;
    		   if(matrix[i][j]=='1' && count==0)
    		   { count=1;
    		     }
    		   
    		  if(i+1<matrix.length && j+1<matrix[i].length){ 
    			  //avoid index out of boundary.   
    		   if( matrix[i][j]=='1' && matrix[i][j+1]=='1'
    		  && matrix[i+1][j]=='1'&& matrix[i+1][j+1]=='1')// if there is a 2x2 Matrix, start to count
    		   {    count=2;
    			   do{ 
    				   for(int c=0;c<=count;c++){
    				  if(i+count<=matrix.length-1 && j+count<=matrix[i].length-1){ 
    					//avoid index out of boundary. 
    					  
    				   if(matrix[i+c][j+count]!='1'||
    					  matrix[i+count][j+c]!='1'){ //if there is any '0' in NxN square.
    				    
    					   current=false;
    					   break;
    					    }
    				   else if(c==count){ //if there is no '0' in NxN square.
    					  
    					   count=count+1; 
    					   
    					   break;}
    				        }
    				   else
    				      
    				      {current=false;
    				         break;
    					   }
    				   }
    			  }while(current);
    		
    	       }}
    		    if(count>FinalNum){
    		    	FinalNum=count;
    		    }
    	        } 
    	return FinalNum*FinalNum ;
    }
    

  • 0
    J

    A bit more concise variant:

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null || matrix.length == 0) {
                return 0;
            }
    
            final int N = matrix.length;
            final int M = matrix[0].length;
            final int[] heights = new int[M];
    
            int max = 0;
    
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(matrix[i][j] == '0') {
                        heights[j] = 0;
                    } else {
                        heights[j]++;
                    }
                }
    
                max = Math.max(max, maxRow(heights));
            }
    
            return max;
        }
        
        private int maxRow(int[] heights) {
            int max = 0;
    
            for(int i = 0; i < heights.length; i++) {
                int minHeight = heights[i];
                for(int j = i; j < heights.length; j++) {
                    if(heights[j] == 0) {
                        break;
                    }
    
                    minHeight = Math.min(minHeight, heights[j]);
                    final int len = Math.min(minHeight, j - i + 1);
                    max = Math.max(max, len * len);
                }
            }
    
            return max;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.