[LeetCode] Maximal Square

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 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.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Solution: Dynamic Programming.

We look at the maximal square ending at (i, j), for each pair i, j. The global maximal square will be realized at one of such maximal squares.

Let f(i, j) denote the side length of the maximal square ending at (i, j).

Two cases:

1. matrix[i][j] is '0'. 
    Trivial. f(i, j) = 0.

2. matrix[i][j] is '1'. 
    f(i, j) = min{ f(i - 1, j), f(i, j - 1), f(i - 1, j - 1) } + 1.
Time Complexity: O(mn), where m x n is the size of the matrix.
Space Complexity: O(mn) if we implement it naively, where m x n is the size of the matrix. It can be improved to O(min{m, n}). 
Code in Java: O(mn) time complexity, O(mn) space complexity. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

public class Solution { public int maximalSquare(char[][] matrix) { int m = matrix.length; if (m == 0) { return 0; } int n = matrix[0].length; int max_so_far = 0; int[][] max_ending_here = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '0') { max_ending_here[i][j] = 0; continue; } //Now matrix[i][j] == '1' if (i == 0 || j == 0) { max_ending_here[i][j] = 1; } else { max_ending_here[i][j] = Math.min( Math.min( max_ending_here[i][j - 1], max_ending_here[i - 1][j] ), max_ending_here[i - 1][j - 1] ) + 1; } if (max_so_far < max_ending_here[i][j]) { max_so_far = max_ending_here[i][j]; } } } return max_so_far * max_so_far; } }

Code in Java: O(mn) time complexity, O(n) space complexity. This can be easily improved to O(min{m, n}) by comparing m and n first, and then deciding the order of the two loops.

public class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) { return 0; }
        int n = matrix[0].length;
        int max_so_far = 0;
        int[] max_ending_here = new int[n];
        Arrays.fill(max_ending_here, 0);
        int upper_left_max_ending_here = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    upper_left_max_ending_here = max_ending_here[j];
                    max_ending_here[j] = 0;
                    continue;
                } 
                //Now matrix[i][j] == '1'
                if (i == 0 || j == 0) {
                    upper_left_max_ending_here = max_ending_here[j];
                    max_ending_here[j] = 1;
                } else {
                    int tmp = max_ending_here[j];
                    max_ending_here[j] = Math.min(
                         Math.min(
                             max_ending_here[j - 1], 
                             max_ending_here[j]
                         ),
                         upper_left_max_ending_here
                    ) + 1;
                    upper_left_max_ending_here = tmp;
                }
                if (max_so_far < max_ending_here[j]) {
                   max_so_far = max_ending_here[j];
                }
            }
        }
        return max_so_far * max_so_far;
    }
}