Matrix 01
- 2 min read
- Array
- Graph
- Matrix
- LC-Medium
3 years ago
Solution
- Similar to Rotting Oranges, we use Multi-Source Breadth-first Search
- Do Multi-source BFS starting from every:
- Initially, add all zeroes to queue and mark as visited. Each element in queue is
(r, c, dist)wheredistis distance to nearest 0. - Do BFS, update distance wherever needed
- Each iteration, if a node was not seen, we update it's distance.
- We know that all zeroes don't need to be changed, and they were all marked as visited in the beginning itself.
- So we can go ahead and directly change the values to
dist + 1in the code because whichever nodes were not in the visited set, were initially not zeroes, which means they're cells which we possibly might have to change.
- Initially, add all zeroes to queue and mark as visited. Each element in queue is
Data Structures & Algorithms#^d8d193
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(mn) |
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
q = deque()
vis = set()
nrows, ncols = len(mat), len(mat[0])
for r in range(nrows):
for c in range(ncols):
if mat[r][c] == 0:
q.append((r, c, 0))
while q:
for _ in range(len(q)):
r, c, dist = q.popleft()
if (r, c) not in vis:
vis.add((r, c))
mat[r][c] = dist
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nr, nc = r + dr, c + dc
if nr >= 0 and nr < nrows and nc >= 0 and nc < ncols and (nr, nc) not in vis:
q.append((nr, nc, dist + 1))
return mat