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

# 67 / 67 test cases passed.
# Status: Accepted
# Runtime: 80 ms``````

• 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
``````

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

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

• 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

• @jedihy same question

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