Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Thought Process
BFS
Store 0's in the queue so we can look at their neighbors
Solution
from collections import deque
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
q = deque()
visited = set()
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
q.append([i,j])
visited.add((i,j))
d = [[1,0], [-1, 0], [0,1], [0,-1]]
while q:
node = q.popleft()
x = node[0]
y = node[1]
for i in d:
newX = x+i[0]
newY = y+i[1]
if newX < 0 or newX >= len(matrix) or newY >= len(matrix[0]) or newY < 0 or (newX, newY) in visited:
continue
matrix[newX][newY] = matrix[x][y]+1
q.append([newX, newY])
visited.add((newX, newY))
return matrix
from collections import deque
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
q = deque()
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
q.append([i,j])
else:
matrix[i][j] = float('inf')
d = [[1,0], [-1, 0], [0,1], [0,-1]]
while q:
node = q.popleft()
x = node[0]
y = node[1]
for i in d:
newX = x+i[0]
newY = y+i[1]
if newX < 0 or newX >= len(matrix) or newY >= len(matrix[0]) or newY < 0 or matrix[newX][newY] <= matrix[x][y]+1:
continue
matrix[newX][newY] = matrix[x][y]+1
q.append([newX, newY])
return matrix
Notice here we don't care about the "deepest level" or using levels in anyways (like in Rotting Oranges or As Far Land As Possible). This is why we don't utilize the levels in this BFS problem
Time Complexity
Time: O(n*n)
Space: O(n*n) since we are storing all the 0's and 1's in the queue
