The example problem
In a grid with blocked cells, find the fewest steps from a start cell to a target cell, moving up, down, left or right.
Input: the pond shown (tap pads to add rocks) Output: the length of the shortest hop path, or “no path”
Picture it
Picture a frog on a pond of lily pads that wants to reach a fly, avoiding rocks. Drop a stone at the frog and watch the ripple: it reaches all pads 1 hop away, then all pads 2 hops away, and so on. The first ripple that reaches the fly gives the shortest number of hops. A queue holds the pads on the current ripple edge.
The key idea
Breadth-first search explores in distance order, so the first arrival is the shortest path in an unweighted grid.
Python
def shortest_path(pond, start, goal):
q, steps = deque([start]), 0
seen = {start}
while q:
for _ in range(len(q)):
pad = q.popleft()
if pad == goal:
return steps
for nxt in neighbours(pad):
if is_pad(nxt) and nxt not in seen:
seen.add(nxt)
q.append(nxt)
steps += 1
return -1Practise queue · bfs
- LeetCode 102Binary Tree Level Order TraversalA family photo, one generation per row
- LeetCode 103Zigzag Level Order TraversalA family photo read like a snake
- LeetCode 107Level Order Traversal IIGenerations listed youngest first
- LeetCode 200Number of IslandsPainting islands on a sea chart
- LeetCode 695Max Area of IslandMeasuring the biggest island
- LeetCode 994Rotting OrangesRot spreading through a fruit crate
- LeetCode 407Trapping Rain Water IIRain on a block city, filled from the edges
NeetCode 150 problems that use it
Graphs ·
- LeetCode 200 · MediumNumber of IslandsPainting islands on a sea chart
- LeetCode 133 · MediumClone GraphPhotocopying a city map junction by junction
- LeetCode 695 · MediumMax Area of IslandMeasuring the biggest island
- LeetCode 417 · MediumPacific Atlantic Water FlowRain on an island draining to two oceans
- LeetCode 130 · MediumSurrounded RegionsCapturing surrounded stones on a Go board
- LeetCode 994 · MediumRotting OrangesRot spreading through a fruit crate
- LeetCode 286 · MediumWalls and GatesDistance from every room to the nearest exit
- LeetCode 207 · MediumCourse ScheduleCan every course be taken?
- LeetCode 210 · MediumCourse Schedule IIA timetable that respects every prerequisite
- LeetCode 684 · MediumRedundant ConnectionThe one cable too many
- LeetCode 323 · MediumNumber of Connected Components in an Undirected GraphCounting circles of friends
- LeetCode 261 · MediumGraph Valid TreeIs this network a tree?
- LeetCode 127 · HardWord LadderChanging one letter at a time