Explore graph interview patterns with animated BFS, DFS, union-find and topological sort on grids, courses and word ladders. Study each step and Python solutions.
The pattern
Graphs: things and the connections between them
A graph is nodes joined by edges. Most graph problems come down to a search: DFS (recursion or a stack) to explore everything reachable, BFS (a queue) when distance in steps matters, and union-find when connections arrive one at a time. The hard part is often spotting the graph: grid cells, courses, words.
1A grid is a graph
Each cell is a node, joined to the cells beside it (up, down, left, right). Islands, oranges, gates and oceans are all graph searches on that hidden graph.
2BFS goes in rings
BFS (a queue) reaches everything 1 step away, then 2, then 3. So it finds shortest paths when every step costs the same, and starting it from many sources at once gives each cell its nearest source.
3Arrows and cycles
Dependencies are arrows: take b before a. A valid order exists exactly when there's no cycle. DFS finds one by meeting a node that's still on its current path.
How to spot which tool
- Count or measure regions: scan, and flood-fill (DFS or BFS) from each unvisited start.
- Fewest steps / nearest source: BFS, seeded with every source at once if there are several.
- Dependencies, ordering: a directed graph; DFS with an on-path set finds cycles and a topological order.
- “Already connected?” as edges arrive: union-find.
Reading the pictures
- Grid problems colour the cells; the queue or DFS stack is shown as a row above.
- Other problems draw the graph: arrows for directed edges, dashed edges for ones not added yet, “root” under union-find roots.
- To build and search your own graph, see the Graph page; for Kahn's algorithm, see Topological Sort.
NeetCode 150 · Graphs
All 13 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Number of Islands
MediumBlind 75Given a grid of '1' (land) and '0' (water), count the islands. An island is land joined up, down, left or right; the grid's edges are water.
grid = [11000, 11000, 00100, 00011]
BFS queue
grid: 1 = land, 0 = water
variables
- islands
- 0
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(rows × cols)
- 41 ops
- Brute force
- n/a
Every cell has to be looked at, so O(rows × cols) is already the best possible. (The answer is cross-checked with union-find, a different method.)
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Number of Islands
Step by step
- Cell taken from the queue
- Waiting in the queue
- Island being flooded
- Islands already counted
- Water
Press Start or Step: the step the animation is on lights up below.
- 1
Scan every cell
for r in range(rows): for c in range(cols): - 2
Unvisited land → a new island
if grid[r][c] == '1' and (r, c) not in visit: bfs(r, c); islands += 1 - 3
BFS: claim the land neighbours
row, col = q.popleft(); for dr, dc in directions: if land and not visited: q.append(...); visit.add(...) - 4
Queue empty: island complete
- 5
Scan finished
return islands
A grid is a graph: each land cell is a node, joined to the land cells beside it. Counting islands is counting connected components.
Scan every cell. When you meet land that hasn't been visited, that's a new island: add 1, then flood it with BFS (or DFS), marking every land cell it reaches as visited, so the rest of that island is never counted again.
Spot it in an interview
- “Count regions / groups / components” on a grid: scan, and flood-fill from each unvisited start.
- BFS uses a queue; DFS (recursion) works just as well here.
Each cell is scanned once and enters the queue at most once.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.