One scan beat 80% with O(n) space and O(n^2) space solution


  • 1
    F

    One Scan initial O(n^2) space solution: beat 80%

    If operation is cheap, so I put initial state inside of if(matrix[i][j] == '1').
    Whenever it's on the leftmost column or uppermost row, init memory table as 1.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int rows = matrix.length;
            int cols = matrix[0].length;
            int[][] lenMatrix = new int[rows][cols];
            
            int max = 0;
            for(int i = 0; i < rows; i++){
                for(int j = 0; j < cols; j++){
                    if(matrix[i][j] == '1'){
                        if(i == 0 || j == 0){
                            lenMatrix[i][j] = 1;
                        }else{
                            lenMatrix[i][j] = Math.min(Math.min(lenMatrix[i-1][j-1],lenMatrix[i][j-1]),lenMatrix[i-1][j]) + 1;
                        }
                        max = Math.max(max, lenMatrix[i][j]);
                    }
                }
            }
            
            return max*max;
        }
    }
    

    One scan O(n) solution based on previous solution.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int rows = matrix.length;
            int cols = matrix[0].length;
            //int[][] lenMatrix = new int[rows][cols];
            
            int[] pre = new int[cols];
            int[] cur = new int[cols];
            
            int max = 0;
            for(int i = 0; i < rows; i++){
                pre = cur;
                cur = new int[cols];
                for(int j = 0; j < cols; j++){
                    if(matrix[i][j] == '1'){
                        if(i == 0 || j == 0){
                            cur[j] = 1;
                        }else{
                            cur[j] = Math.min(Math.min(pre[j], pre[j-1]), cur[j-1]) + 1;
                        }
                        max = Math.max(max, cur[j]);
                    }
                }
            }
            
            return max*max;
        }
    }
    

Log in to reply
 

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