Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Tips:

DP, O(mn) Space, O(mn) time

Top, Left, and top Left decides the size of the square. If all of them are same, then the size of square increases by 1. If they're not same, they can increase by 1 to the minimal square.

可优化空间到O(m)或O(n)。这里优化完是O(n)

Code：

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] result = new int[m][n];
        int max = 0;
        //initialize
        for (int i = 0; i < m; i++) {
            result[i][0] = matrix[i][0] == '1' ? 1 : 0;
            max = Math.max(max, result[i][0]);
        }
        for (int i = 0; i < n; i++) {
            result[0][i] = matrix[0][i] == '1' ? 1 : 0;
            max = Math.max(max, result[0][i]);
        }
        //dp: top, Left, and Top Left decides the size of the square. If all of them are same, then the size of square increases by 1. If they're not same, they can increase by 1 to the minimal square.
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    result[i][j] = Math.min(result[i - 1][j], Math.min(result[i][j - 1], result[i - 1][j - 1])) + 1;
                }
                max = Math.max(max, result[i][j]);
            }
        }
        return max * max;
    }
}

优化空间：

public int maximalSquare(char[][] matrix){
    // write your code here
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int max = 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int [][]result = new int [2][n];
    for(int i = 0; i < m; i++){
        result[i % 2][0] = matrix[i][0] == '1' ? 1 : 0;
        max = Math.max(result[i%2][0] , max);
        for(int j = 1; j < n; j++) {
            if(i > 0) {
                if(matrix[i][j] =='1') {
                    result[i%2][j] = Math.min(result[(i - 1)%2][j],Math.min(result[i%2][j-1], result[(i-1)%2][j-1])) + 1;
                } else {
                    result[i%2][j] = 0;
                }
            }
            else {
                result[0][j] = matrix[0][j] == '1' ? 1 : 0;
            }
            max = Math.max(result[i%2][j], max);
        }
    }
    return max * max;
}