O(N^2) with no extra space solution.


  • 0
    V
    public int maximalSquare(char[][] matrix) {
    	if(matrix == null || matrix.length == 0) {
    		return 0;
    	}
    	
    	int n = matrix.length;
    	int m = matrix[0].length;
    	
               char max = '0';
    	
                //See if there is any 1in first row and first column
    
    	for(int i = 0; i< n && max == '0'; i++) {
    		max |= (matrix[i][0] - '0');			
    	}
    	
    	for(int i = 0; i< m && max == '0'; i++) {
    		max |= (matrix[0][i] - '0');			
    	}
    	
    	
    	for(int i = 1;i<n; i++) {
    		for(int j = 1; j<m; j++) {
    			if(matrix[i][j] == '1') {
                                        // Take the min character
    				char a = (char) Math.min(matrix[i-1][j-1], Math.min(matrix[i-1][j], matrix[i][j-1]));
                                        
                                        // Update the value                 
    				matrix[i][j] = (char) (a + 1);
    
                                        //Maintain a max
    				if(matrix[i][j] > max) {
    					max  = matrix[i][j];
    				}
    			}
    		}
    	}
    	
    	return (max -'0') * (max -'0');
    }

Log in to reply
 

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