Intuition
- The approach here is multi-source BFS.
- Starting from each gate, run BFS. To do so initialize your BFS queue with each of the respective gates.
- DFS would result in a greater runtime since
Complexity
Runtime
since there are MN total cells in the grid, and we are touching each cell only once due to the visited set.
Space
since the visited set or the queue could have MN items, for example if the entire grid contains only gates.
Code
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
m, n = len(rooms), len(rooms[0])
# Linear scan to find the gates
q = deque()
for r in range(m):
for c in range(n):
if rooms[r][c] == 0:
q.append((r, c))
def adj(r, c):
adjacent = []
for i, j in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= i < m and 0 <= j < n:
adjacent.append((i, j))
return adjacent
# Do BFS one step at a time from each of the respective gates
visited = set()
while q:
for _ in range(len(q)):
r, c = q.popleft()
for i, j in adj(r, c):
if rooms[i][j] > 0 and (i, j) not in visited:
rooms[i][j] = rooms[r][c] + 1
q.append((i, j))
visited.add((i, j))