Python DP solution O(n)

• For this question, we only need to consider 4 direction, up, down ,left and right.
so, first, I go through this matrix from top-left to down-right, and we can find the minimum distance from up and left, then, go through the matrix from down-right to top-left, so we can find the minimum distance from down and right. and it said the elements will not exceed 10,000, so I just set the initial value as 10,000.

``````    def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
dic = {}
if not matrix or not matrix[0]:
return matrix
h,w = len(matrix),len(matrix[0])
mask = [[10000]*w for i in xrange (h)]
for i in xrange (h):
for j in xrange (w):
if matrix[i][j] != 0:
else:
for i in xrange (h-1,-1,-1):
for j in xrange (w-1,-1,-1):
if matrix[i][j] != 0:
if i < h-1:
if j < w-1:
``````

If you have any better idea, please let me know! Thanks!

• can you explain a bit how you got to the conclusion of iterating twice through the matrix?

• @robinenrique
For the first time of iteration, we go through the matrix from top to down , left to right:
mask[i][j] will record the minimum distance from i,j to the nearest 0 from up and left.

For the second time of iteration, we go through the matrix from down to top , right to left:
mask[i][j] will record the minimum distance from i,j to the nearest 0 from down and right and up and left(which is already store in mask[i][j]) .

Is it clear?

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