Implicit graph (states as nodes)

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A padlock has two wheels, each showing a digit 0 to 9, and starts at 00. One move turns one wheel up or down by one, and wheels wrap, so 0 goes down to 9. Some combinations are dead ends that jam the lock: say 10 and 01. What is the fewest moves to reach 99? By hand: 00 → 90 → 99, two moves, going "down" twice. You found it by thinking of the combinations you could reach in one move, then two.

That is breadth-first search. The difference from a usual graph problem is that nobody gave you a list of nodes and edges. There are 100 combinations and 400 possible moves, and for a 4-wheel lock 10,000 combinations and 80,000 moves. Writing them all down first would waste time and memory on states you never visit.

Build the structure, one piece at a time

Piece one: decide what a state is. Here, the string of digits on the wheels, such as "00". A state is a node.

Piece two: a rule that produces neighbours on demand instead of a stored list: for each wheel, make two copies of the state, one with that digit +1 and one with −1, wrapping 9 and 0. From "00" the rule gives 10, 90, 01, 09. That rule is the whole edge list; it just has not been written out.

Piece three: ordinary BFS with a queue and a visited set, plus a dead-end set to refuse.

Why it is correct

BFS takes states out of the queue in order of the number of moves used to reach them: all 0-move states, then 1-move, then 2-move. So the first time the target is generated, no shorter route exists; a shorter route would have generated it in an earlier layer. The visited set stops the search from going round in circles, which matters because wheels wrap. The neighbour rule must produce exactly the legal moves, no more and no fewer, and that is the only place the problem's details enter.

Why it is fast

Each state is visited at most once, and each visit runs the rule once, producing a fixed number of neighbours b. For w wheels:

states = 10^w, work ≈ 10^w · 2w

For four wheels that is about 80,000 steps. Trying move sequences without a visited set would be 8 to the power of the path length, with no bound at all.

How to recognise it in an interview

Cues: "fewest operations to transform X into Y", "each step changes one letter / one digit / one unit", "minimum moves", with no graph given. The first thing to say: "the states form a graph I never need to store; I will BFS with a function that generates neighbours." Open the Lock is the example above. Word Ladder is the same with words as states and "change one letter to make another dictionary word" as the rule. Minimum Genetic Mutation is Word Ladder with an alphabet of four letters.

02The idea in one line

Define neighbours by a rule instead of an adjacency list; search as usual.

Reach for it when: Word ladder, open the lock, minimum genetic mutation, water jug, guess the word.

Cost: O(states · branching) time.

03The walk-through, step by step

The video works one example: Open the Lock from 0000 to 0202 avoiding dead ends. These are its captions in order, so you can follow without the video or check a step you missed.

1. No adjacency list: a state's 4 neighbours are made by turning one wheel ±1
2. Start at 00, 0 turns; visited = {00}
3. Pop 00 (0 turns): generate its four neighbours
4. push 90, 09; 10, 01 dead
5. Pop 90 (1 turns): generate its four neighbours
6. push 80, 91, 99; 00 seen
7. 99 found at distance 2: the first visit is the shortest path
8. Each state visited once, 4 moves each: O(10^w · w) for w wheels

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map.