My accepted java bottom-up dp solution


  • 0
    M

    Time complexity: O(m*n), Space complexity: O(m * n)

    I used a int[][] maxmatrix to store local max length of side of maximal square for each cell and use 'max' to store the global max length of side.

    Steps for general cases:

    1. copy last row and last col to maxmatrix, get global max initial value
    2. then in matrix, from matrix[matrix.length - 2][matrix[0].length - 2] to the left corner,

      if the cell is '1', in maxmatrix, find the min of adjacent three cells and add the min to the current value. compare with global max, keep it or update it.

      if the cell is '0', keep maxmatrix cell value 0.
    3. return the max^2.
       public int maximalSquare(char[][] matrix) {
    
        	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        		return 0;
        	} else if (matrix.length == 1) { 
        		return rowMax(matrix);
        	} else if (matrix[0].length == 1) { 
        		return colMax(matrix);
        	}
        	
        	int[][] maxmatrix = new int[matrix.length][matrix[0].length];
        	int max = copyMatrix(matrix, maxmatrix);
        	
        	for (int i = matrix.length - 2; i >= 0; i--) { 
    			for (int j = matrix[0].length - 2; j >= 0; j--) { 
    				if (matrix[i][j] == '1') {
    					maxmatrix[i][j] = findMin(maxmatrix[i + 1][j], maxmatrix[i + 1][j + 1], maxmatrix[i][j + 1]) + 1;
    					max = (maxmatrix[i][j] > max) ? maxmatrix[i][j]: max;
    				}
    			}
    		}    	
        	return (int) Math.pow(max, 2);
        }
        
        public int rowMax(char[][] matrix) {
        	for (int i = 0; i < matrix[0].length; i++) {
    			if (matrix[0][i] == '1') {
    				return 1;
    			}
    		}
        	return 0;
        }
        
        public int colMax(char[][] matrix) {
        	for (int i = 0; i < matrix.length; i++) {
    			if (matrix[i][0] == '1') {
    				return 1;
    			}
    		}
        	return 0;
        }
        
        public int copyMatrix(char[][] matrix, int[][] maxmatrix) {
        	int max = 0;
        	for (int col = 0; col < matrix[0].length; col++) {
        		maxmatrix[matrix.length - 1][col] = matrix[matrix.length - 1][col] - '0'; 
        		if (max == 0 && maxmatrix[matrix.length - 1][col] == 1) {
        			max = 1;
        		}
        	}
        	for (int row = 0; row < maxmatrix.length - 1; row++) {
    			maxmatrix[row][maxmatrix[0].length - 1] = matrix[row][matrix[0].length - 1] - '0';
    			if (max == 0 && maxmatrix[row][maxmatrix[0].length - 1] == 1) {
    				max = 1;
    			}
    		}
        	
        	return max;
        }
        
        public int findMin(int a, int b, int c) {
        	return Math.min(Math.min(a, b), c);
        }

Log in to reply
 

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