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
Python 80ms DP solution beats 100% O(mn) time one pass


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 byrow 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

@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 * kI have no idea why this works... Could you please explain? I am having trouble understanding