Java O(n^2) time O(n) space


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

Log in to reply
 

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