Java 8ms/Python 112 ms DP solution. O(mn) time one pass


  • 2

    My logic is a bit different than others. Still dynamic programming. a is the side length of current maximum square found. dp[i][j+1] is the side length of maximum square with matrix[i][j] as the lower right corner. dp is reduced from a matrix to a vector since new values of dp[i][j+1] only depend on it's up and left neighbor. k is the minimum side length of the two neighbor squares.

    (1)   dp[i][j+1] = 0         if matrix[i][j] == '0'
    (2)   dp[i][j+1] = k+1       if matrix[i][j] == '1' and matrix[i-k][j-k] =='1'
    (3)   dp[i][j+1] = k         otherwise
    

    Java

    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] dp = new int[n + 1];
        int a = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '0')
                    dp[j + 1] = 0;
                else {
                    int k = Math.min(dp[j], dp[j + 1]);
                    if (matrix[i - k][j - k] == '1') ++k;
                    dp[j + 1] = k;
                    a = Math.max(a, k);
                }
            }
        return a * a;
    }
    //Runtime: 8 ms
    

    Python

    def maximalSquare(self, matrix):
        if not matrix:
            return 0
        a, m, n = 0, len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        for i in xrange(m):
            for j in xrange(n):
                if matrix[i][j] == '0':
                    dp[j + 1] = 0
                else:
                    k = min(dp[j], dp[j + 1])
                    if matrix[i - k][j - k] == '1':
                        k += 1
                        a = max(a, k)
                    dp[j + 1] = k
        return a * a
    
    # Runtime: 112 ms

  • 0
    H

    Try test case [[0,1,1,0],[0,1,1,0],[0,0,0,0]], I think your code output 1.


  • 0

    I just tested this. It is 4. And here are some of my tests.

    ['0110', '0110', '0000'] 4
    ['11', '11'] 4
    ['01101', '11010', '01110', '11110', '11111', '00000'] 9
    ['101101', '111111', '011011', '111010', '011111', '110111'] 4
    ['1111', '1111', '1111'] 9

  • 0
    Y
    This post is deleted!

Log in to reply
 

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