Python 80ms DP solution beats 100% O(mn) time one pass


  • 3
    C
    class Solution(object):
        def maximalSquare(self, matrix):
            if (not matrix) or (not matrix[0]):
                return 0
            n = len(matrix)
            m = len(matrix[0])
            widths = [0] * n
            k = 0
            for j in xrange(0, m):
                max_continous_k = 0
                continous_k = 0
                for i in xrange(0, n):
                    if matrix[i][j] == '1':
                        widths[i] += 1
                    else:
                        widths[i] = 0
                    if widths[i] > k:
                        continous_k += 1
                        max_continous_k = max(continous_k, max_continous_k)
                    else:
                        continous_k = 0
                if max_continous_k > k:
                    k += 1
            return k * k
            
            
    # 67 / 67 test cases passed.
    # Status: Accepted
    # Runtime: 80 ms

  • 2
    D

    Great idea!

    I've changed your code a little. I think it is more concise and easier to understand

    class Solution(object):
        def maximalSquare(self, matrix):
            """
            :type matrix: List[List[str]]
            :rtype: int
            """
            rows, max_size = len(matrix), 0
            '''
            size[i]: the current number of continuous '1's in a column of matrix. Reset when discontinued.
            The idea is to do a by-row scan, updating size[i]
            Then check if there are continuous elements in size whose value is bigger than current maximal size.
            '''
            if rows > 0:
                cols = len(matrix[0])
                size = [0] * cols
                for x in xrange(rows):
                    # update size
                    count, size = 0, map(lambda x, y: x+1 if y == '1' else 0, size, matrix[x])
                    for y in xrange(cols):
                        # check if it exceeds current maximal size
                        if size[y] > max_size:
                            count += 1
                            if count > max_size:
                                # increase maximal size by 1
                                max_size += 1
                                break
                        else:
                            count = 0
    
            return max_size*max_size
    

  • 0

    Hello, you must be the author of ss. This solution is really fast.


  • 0

    I don't why there is a break after max_size += 1. Could you explain it?


  • 0
    L

    @clowwindy said in Python 80ms DP solution beats 100% O(mn) time one pass:

    class Solution(object):
    def maximalSquare(self, matrix):
    if (not matrix) or (not matrix[0]):
    return 0
    n = len(matrix)
    m = len(matrix[0])
    widths = [0] * n
    k = 0
    for j in xrange(0, m):
    max_continous_k = 0
    continous_k = 0
    for i in xrange(0, n):
    if matrix[i][j] == '1':
    widths[i] += 1
    else:
    widths[i] = 0
    if widths[i] > k:
    continous_k += 1
    max_continous_k = max(continous_k, max_continous_k)
    else:
    continous_k = 0
    if max_continous_k > k:
    k += 1
    return k * k

    I have no idea why this works... Could you please explain? I am having trouble understanding


  • 0
    S

    @jedihy same question


Log in to reply
 

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