Skip to main content

BFS

Breadth-first search on a grid expands in layers: every cell at distance d is processed before any cell at distance d + 1. That layering is what makes BFS the tool for shortest-path and elapsed-time questions, where DFS answers "reachable?" but not "how far?" - see Grids as Graphs and why BFS's first arrival is shortest.

Multi-Source BFS​

Seed the queue with every starting cell at distance 0 rather than running one BFS per source, and the layers measure distance to the nearest source. The last layer popped is the answer.

994. Rotting Oranges​

Medium·
3 Approaches
FIG. 994 ROTTING ORANGES BFS● INTERACTIVE
visualization loads as you reach it
import collections
from typing import List
 
 
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
"BFS"
 
def getRottenIndices():
indices = []
good_count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
indices.append((i, j, 0))
good_count += grid[i][j] == 1
return indices, good_count
 
m, n = len(grid), len(grid[0])
indices, good_count = getRottenIndices()
 
queue = collections.deque(indices)
visited = set()
maxi = 0
 
isValidIndex = lambda i, j: (0 <= i < m) and (0 <= j < n)
 
while queue:
i, j, minute = queue.popleft()
if (i, j) not in visited and isValidIndex(i, j):
visited.add((i, j))
maxi = max(maxi, minute)
good_count -= grid[i][j] == 1
for a, b in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
if isValidIndex(a, b) and grid[a][b] == 1:
queue.append((a, b, minute + 1))
 
return maxi if good_count == 0 else -1

542. 01 Matrix​

Medium·
FIG. 542 01 MATRIX BFS● INTERACTIVE
visualization loads as you reach it
import collections
from typing import List
 
 
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
def getStartIndices():
indices = []
for i in range(n):
for j in range(m):
if mat[i][j] == 0:
indices.append((i, j, 0))
res[i][j] = 0
return indices
 
n, m = len(mat), len(mat[0])
res = [[n * m] * m for i in range(n)]
queue = collections.deque(getStartIndices())
isValidIndex = lambda i, j: 0 <= i < n and 0 <= j < m
visited = set()
while queue:
i, j, distance = queue.popleft()
res[i][j] = min(res[i][j], distance)
if (i, j) not in visited:
visited.add((i, j))
for a, b in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
if isValidIndex(a, b):
queue.append((a, b, distance + 1))
return res

Single-Source BFS​

From one cell, the same layering answers "shortest distance from here to there?" - and nothing stops a layer spreading in 8 directions instead of 4, as long as neighbours yields them all.

1091. Shortest Path in Binary Matrix​

Medium·
2 Approaches
FIG. 1091 SHORTEST PATH BINARY MATRIX BFS● INTERACTIVE
visualization loads as you reach it
import collections
from typing import List
 
 
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
def neighbors(i, j):
for p in (-1, 0, 1):
for q in (-1, 0, 1):
if p == q == 0:
continue
yield i + p, j + q
 
if grid[0][0] != 0 or grid[-1][-1] != 0:
return -1
n = len(grid)
queue = collections.deque([(0, 0, 1)])
visited = set()
mini = n * n
 
isValidIndex = lambda i, j: 0 <= i < n and 0 <= j < n
while queue:
i, j, distance = queue.popleft()
if i == j == n - 1:
return min(mini, distance)
if (i, j) not in visited:
visited.add((i, j))
for a, b in neighbors(i, j):
if isValidIndex(a, b) and grid[a][b] == 0:
queue.append((a, b, distance + 1))
return -1