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 Approachesclick to switch
Explanation

Seed the queue with every already-rotten cell at minute 0, so all sources spread in lockstep and each popped cell carries the minute it rots. A visited set keeps the first (and therefore earliest) arrival at each cell and drops the rest. maxi tracks the last minute reached, and good_count counts fresh oranges still standing, so a non-zero count at the end means some orange was unreachable.

Analysis
Time
O(2×m×n)
  • getRottenIndices is a full grid scan to seed the queue and count fresh oranges - one O(m×n) pass.
  • The BFS loop then processes every cell (each enqueued a bounded number of times but touched once through the visited guard) - a second O(m×n) pass.
Space
O(2×m×n)
  • queue holds up to every cell in the worst case - O(m×n).
  • visited also holds up to every cell - another O(m×n).
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·
Explanation

Seed the queue with every 0 cell at distance 0, so all sources spread in lockstep and each popped cell carries the distance it was reached at. res starts filled with the worst-case distance n*m and is lowered to the first (and therefore shortest) distance each cell is popped with. A visited set stops a cell from being expanded twice.

Analysis
Time
O(m×n)
  • Each cell is enqueued once per zero-distance neighbour (at most 4 times) and processed once, so the work is linear in the number of cells.
Space
O(m×n)
  • The queue, the visited set, and the res matrix all hold up to every cell.
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 Approachesclick to switch
Explanation

neighbors yields all 8 surrounding cells (orthogonal and diagonal). The queue starts at (0, 0, 1), and each popped cell that hasn't been visited enqueues its open (0) neighbours at distance + 1. Because BFS explores in layers, the first time (n-1, n-1) is popped it carries the shortest distance.

Analysis
Time
O(n²)
  • Each of the n² cells is visited once and expands to at most 8 neighbours.
Space
O(n²)
  • The queue and the visited set both hold up to every cell.
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