Clean and short java solution O(n) space


  • 0
    S
    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if (matrix.length == 0) return 0;
            int row = matrix.length, col = matrix[0].length, max = 0;
            int[] curr = new int[col];
            int[] prev = new int[col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    int val = matrix[i][j]-'0';
                    if (i == 0 || j == 0) curr[j] = val;
                    else if (val == 1) {
                        curr[j] = Math.min(Math.min(curr[j-1], prev[j]), prev[j-1])+1;
                    } else if (val == 0) {
                        curr[j] = 0;
                    }
                    max = Math.max(max, curr[j]);
                }
                prev = curr.clone();
            }
            return max*max;
        }
    }

Log in to reply
 

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