Builds on Shortest-Path BFS, which you haven’t finished yet.
BFS on an Implicit State Graph (incl. Bidirectional BFS)
Open the Lock (LC 752)(opens leetcode.com)
A lock has 4 wheels side by side, and each wheel shows one digit from '0' to '9'. One move turns a single wheel by one position, up or down, and the wheels wrap around: turning up from '9' shows '0', and turning down from '0' shows '9'. The lock begins at "0000", and what it displays is always a 4-character string.
deadends lists codes that jam the lock: as soon as the display shows one of them, the wheels can't be turned any more and the lock can't be opened. Return the smallest number of moves that makes the display show target without ever showing a code from deadends, or -1 when no sequence of moves can do it.
State-Space BFS
start configuration âž” build neighbour configurations âž” BFS depth = fewest moves| 1 | from collections import deque |
| 2 | from typing import Callable, Hashable, Iterable, List |
| 3 | Â |
| 4 | Â |
| 5 | def fewest_moves(start: Hashable, is_goal: Callable[[Hashable], bool], next_states: Callable[[Hashable], Iterable[Hashable]], blocked: Iterable[Hashable] = ()) -> int: |
| 6 | """State-Space BFS: the fewest moves from start to a goal state, on a graph built one state at a time, or -1. |
| 7 | Precondition: every move costs one step, and a state holds everything that decides the moves ahead. |
| 8 | next_states(state) yields the states one move away. blocked states may never be entered. |
| 9 | V = reachable states. T = the cost of one next_states or is_goal call (it yields at most T states). |
| 10 | B = the cost of putting the blocked states into seen. |
| 11 | Time: O(B + V * T) | Space: O(B + V) states |
| 12 | """ |
| 13 | seen = set(blocked) # a blocked state may never be entered, so it is treated as already seen |
| 14 | # 1. Check the Start State Itself: |
| 15 | # Nothing else in the loop tests start, since it is pushed before the loop |
| 16 | # begins, so this guard is the only thing standing between a blocked start and |
| 17 | # a wrong answer. |
| 18 | if start in seen: |
| 19 | return -1 |
| 20 | seen.add(start) |
| 21 | queue = deque([(start, 0)]) # (state, steps taken to reach it) |
| 22 | Â |
| 23 | while queue: |
| 24 | # 2. Pop and Check for the Goal: |
| 25 | # Every move costs exactly 1, so the first time is_goal is true, steps is |
| 26 | # the fewest moves needed — no later pop can report less. |
| 27 | state, steps = queue.popleft() |
| 28 | if is_goal(state): |
| 29 | return steps |
| 30 | Â |
| 31 | # 3. Enqueue Every Unseen Neighbour: |
| 32 | # Marking a neighbour seen at enqueue time, not at pop time, stops it from |
| 33 | # being queued twice while it is still waiting in line. |
| 34 | for neighbor in next_states(state): |
| 35 | if neighbor not in seen: |
| 36 | seen.add(neighbor) |
| 37 | queue.append((neighbor, steps + 1)) |
| 38 | Â |
| 39 | return -1 |
seen holds every dead end and every state ever pushed, so each state enters queue at most once, and queue pops states in non-decreasing order of steps.Write each configuration as one hashable state (here the 4-digit code) and run BFS on a graph that is never stored: pop a state, build each neighbor on the spot by turning one wheel one slot with (digit + move) % 10, and push every neighbor that is not in seen. Every move costs one step, so BFS pops states in order of steps, and the first time target comes off queue its steps is the fewest; putting the dead ends into seen before the search means no move can ever enter one. The trap is a partial key: seen must hold the whole state, here all four wheels, and (row, col, keys) or (row, col, removals_left) when a maze adds keys or wall removals. A later visit that differs only in the left-out part is a different state, and a key without that part skips it as already seen.
See it run
State-Space BFS on a lock, step by step
state 0000steps 0queue 1seen 2
Each column is one wheel. The first row is the popped state. The other rows are the states made by turning that wheel up or down by one slot.
pusheda new state, added to seen and to the queueseena state that seen already holdsdead enda state that may never be entered
Start: seen holds the dead ends "2000" and "0000". The queue holds ("0000", 0).
Gotcha 1 of 4
- The trap
Gotcha 1: Keying
seenon part of the stateMistakeif (nr, nc) not in seen: seen.add((nr, nc))Fixif (nr, nc, nrem) not in seen: seen.add((nr, nc, nrem))What happens:
seen.add(neighbor)must store the whole state. Here that is all four wheels. In Shortest Path in a Grid with Obstacles Elimination (LC 1293), the state is(row, col, removals_left). A later visit to the same cell with more removals left is a different state. Keyed on the cell alone,seenskips it, and the answer is lost.Example: Shortest Path in a Grid with Obstacles Elimination (LC 1293): grid = [[0,0],[1,1],[1,1],[1,0]], k = 2Mistake: returns -1Fix: returns 4
- Where you are is just a cell of a given grid, as in Shortest Path in Binary Matrix (LC 1091): the neighbours are read off the grid, and no state has to be encoded or built. See Shortest-Path BFS
- The states are still built on the spot, but only some moves count, as in Minimum Moves to Move a Box to Their Target Location (LC 1263), where walking is free and each push costs 1: BFS levels no longer equal the answer. See Zero-One BFS
Deep Dive
A state is everything that decides the moves ahead
Shortest-Path BFS already shows that the first pop of the goal is the fewest moves. This card changes only what a node is. A node is a state, and the graph is never stored. The code builds the neighbours of one state at the moment it pops it.
In Open the Lock (LC 752), the state is the four-digit text such as "0000". There are 10^4 = 10,000 states. Each wheel can turn up or down by one slot, so every state has 8 neighbours. The wheel wraps, so (digit + move) % 10 gives 0 after 9 and 9 before 0.
To choose the state, ask this question: if two situations have the same state, do they have the same moves and the same future? If not, a part of the situation is missing from the key.
Example: in Shortest Path in a Grid with Obstacles Elimination (LC 1293), the cell (row, col) is not enough. A visit with 2 removals left can go where a visit with 0 removals left cannot. The state is (row, col, removals_left). For grid = [[0,0],[1,1],[1,1],[1,0]] and k = 2, the full key returns 4 and the key (row, col) returns -1.
One trace: dead ends in seen, and a state that waits in the queue
The board replays openLock(["2000"], "1100"). The answer is 2. The first row is the popped state, and the next two rows are the 8 neighbours, two for each wheel.
seen starts with "2000", so no move can enter that dead end. Then the start "0000" is added. The pop of "0000" pushes 8 states with steps = 1, in this order: "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009".
The pop of "1000" builds "2000", which is a dead end, and "0000", which is in seen. It pushes 6 new states with steps = 2, and "1100" is the first of them.
Later, the pop of "0100" builds "1100" and "9100". Both states are still waiting in queue, but seen already holds them, so neither is pushed a second time. This is the first step marked as the trap on the board. The pops of "0900", "0010", "0090", "0001" and "0009" each repeat it with two more states.
After all 8 states with steps = 1 are popped, "1100" comes to the front. It equals target, so the function returns 2.
Dead ends and the start state
A dead end is a state that may never be entered. The blueprint puts the dead ends into seen before the search. A move to a dead end then fails the test neighbor not in seen, the same test that skips a visited state. No extra check is needed in the loop.
The start is different. The search adds "0000" to seen and to queue before the loop, so the loop never tests it. The guard if "0000" in seen: return -1 must run first. For deadends = ["0000"] and target = "8888", the right answer is -1. Without the guard, the search leaves the dead end and returns 8.
Example: for deadends = [] and target = "0000", the guard passes, the first pop equals target, and the answer is 0.
Wrapping needs % 10. Without it, turning 0 down builds the text "-1000". When that state is popped, int(state[i]) reads "-", and Python raises ValueError. In Java, C++ and C#, write (digit + move + 10) % 10, because -1 % 10 is -1 there.
The cost: states times work per state, and bidirectional search
The card's complexity line is O(B + V * T). V is the number of reachable states, T is the cost of one next_states call, and B is the cost of putting the blocked states into seen.
For openLock, W = 4 wheels. There are at most 10^W states. One state builds 2 * W neighbours, and each neighbour is a new text of W characters, so T = O(W^2). With D dead ends, the total is O(10^W * W^2 + D * W) time.
Example: for the LeetCode example with dead ends ["0201","0101","0102","1212","2002"] and target "0202", the answer is 6, and 822 states are popped. For deadends = [] and target = "5555", the answer is 20, and all 10,000 states are popped.
When the goal state is known and the moves can be undone, bidirectional BFS searches from both ends. It keeps one set of states from start and one from target. Each round it expands the smaller set. It stops when a new neighbor is in the other set. Each side goes about half the depth, so far fewer states are built. This is the method for Word Ladder (LC 127).
60-Second Pitch
"The lock has 10,000 states, and a move turns one wheel by one slot. So I treat each four-digit text as a node and build its 8 neighbours when I pop it, with (digit + move) % 10. I put the dead ends into seen first, so no move can enter one. I also check that "0000" is not a dead end, because the loop never tests the start. Every move costs one step, so BFS pops states in order of steps. The first pop of target is the fewest turns, and an empty queue means -1. The time is O(10^W * W^2 + D * W). If the goal is known, I can search from both ends and expand the smaller side."
Common Questions
- How do you decide what goes into the state?
Put in every value that changes which moves are possible or what the answer is later. Test it with two situations that have the same state: they must have the same future. In Shortest Path in a Grid with Obstacles Elimination (LC 1293), the cell is not enough, and
removals_leftmust be in the key.- Why are the dead ends put into
seenand not checked in the loop? The loop already skips every
neighborthat is inseen. A dead end is a state that may never be entered, which is the same rule for the loop. One set and one test cover both cases. The start needs its own check, because it is pushed before the loop.- What are the time and space complexity of
openLock? O(10^W * W^2 + D * W) time and O(10^W * W + D * W) space, where
Wis the number of wheels andDis the number of dead ends. There are at most 10^W states. Each builds 2 * W neighbours of W characters, andseenstores the states and the dead ends.- When is bidirectional BFS worth using, and how does it stop?
Use it when the goal state is known and a move can be undone, so the search can also start from
target. Keep one set of states from each end, and always expand the smaller set. Stop when a newneighboris in the other set. Add the steps of both sides for the answer.- What changes when the moves have different costs?
The first pop of
targetis then not always the cheapest. A path with more moves can cost less. For general positive costs, use a cheapest-first search with a heap, as in Network Delay Time (LC 743). Thestateidea stays the same.
SWE Reasoning
Spot it
- The question asks for the fewest moves between two configurations, such as a lock code, a word, a board or a pair of values.
- There is no grid or graph in the input. The code has to build the next configurations from the current one.
- Each move changes the configuration a little: one wheel, one letter, one tile.
- Every move costs the same, and some configurations are forbidden, such as dead ends.
- The number of configurations is limited, for example 10^4 lock codes, so a search over all of them is affordable.
The invariant, step by step
seenstarts with every dead end. If"0000"is inseen, the function returns -1.- Otherwise
"0000"is added toseen, andqueueholds("0000", 0). - The loop pops
(state, steps). Ifstate == target, it returnssteps. - It builds the 8 neighbours by turning one wheel one slot with
(digit + move) % 10. - A
neighborthat is not inseenis added toseenand pushed withsteps + 1. A dead end and a visited state are both inseen, so both are skipped. - Each state enters
queueat most once, and the pops come out in non-decreasing order ofsteps. The first pop oftargetis the fewest moves. Ifqueueempties first, the function returns -1.
Traps
- Key is a part of the state. In Shortest Path in a Grid with Obstacles Elimination (LC 1293), a key of
(row, col)skips a later visit with more removals left. For[[0,0],[1,1],[1,1],[1,0]]andk = 2, the answer is -1 instead of 4. Put every value that changes the future moves into the key. - Start in
seenis not checked. The loop never tests"0000". Fordeadends = ["0000"], the search returns 8 instead of -1 fortarget = "8888". - Missing
% 10. Turning 0 down builds"-1000", and the next pop raisesValueError. The same code with% 10returns 1 fortarget = "0009". - Mark at pop time. A state waits in
queuewithout being inseen, so other states push it again. Fortarget = "5555", marking at pop time with a skip for popped states makes 40,001 pushes, and marking at push time makes 10,000. - One-sided search with a known goal. In Word Ladder (LC 127), a search from the start alone builds every level to the full depth. Search from both ends and expand the smaller set.
Practice
Builds on Shortest-Path BFS, which you haven’t finished yet.
BFS on an Implicit State Graph (incl. Bidirectional BFS)
Open the Lock (LC 752)(opens leetcode.com)
A lock has 4 wheels side by side, and each wheel shows one digit from '0' to '9'. One move turns a single wheel by one position, up or down, and the wheels wrap around: turning up from '9' shows '0', and turning down from '0' shows '9'. The lock begins at "0000", and what it displays is always a 4-character string.
deadends lists codes that jam the lock: as soon as the display shows one of them, the wheels can't be turned any more and the lock can't be opened. Return the smallest number of moves that makes the display show target without ever showing a code from deadends, or -1 when no sequence of moves can do it.
State-Space BFS
start configuration âž” build neighbour configurations âž” BFS depth = fewest moves| 1 | from collections import deque |
| 2 | from typing import Callable, Hashable, Iterable, List |
| 3 | Â |
| 4 | Â |
| 5 | def fewest_moves(start: Hashable, is_goal: Callable[[Hashable], bool], next_states: Callable[[Hashable], Iterable[Hashable]], blocked: Iterable[Hashable] = ()) -> int: |
| 6 | """State-Space BFS: the fewest moves from start to a goal state, on a graph built one state at a time, or -1. |
| 7 | Precondition: every move costs one step, and a state holds everything that decides the moves ahead. |
| 8 | next_states(state) yields the states one move away. blocked states may never be entered. |
| 9 | V = reachable states. T = the cost of one next_states or is_goal call (it yields at most T states). |
| 10 | B = the cost of putting the blocked states into seen. |
| 11 | Time: O(B + V * T) | Space: O(B + V) states |
| 12 | """ |
| 13 | seen = set(blocked) # a blocked state may never be entered, so it is treated as already seen |
| 14 | # 1. Check the Start State Itself: |
| 15 | # Nothing else in the loop tests start, since it is pushed before the loop |
| 16 | # begins, so this guard is the only thing standing between a blocked start and |
| 17 | # a wrong answer. |
| 18 | if start in seen: |
| 19 | return -1 |
| 20 | seen.add(start) |
| 21 | queue = deque([(start, 0)]) # (state, steps taken to reach it) |
| 22 | Â |
| 23 | while queue: |
| 24 | # 2. Pop and Check for the Goal: |
| 25 | # Every move costs exactly 1, so the first time is_goal is true, steps is |
| 26 | # the fewest moves needed — no later pop can report less. |
| 27 | state, steps = queue.popleft() |
| 28 | if is_goal(state): |
| 29 | return steps |
| 30 | Â |
| 31 | # 3. Enqueue Every Unseen Neighbour: |
| 32 | # Marking a neighbour seen at enqueue time, not at pop time, stops it from |
| 33 | # being queued twice while it is still waiting in line. |
| 34 | for neighbor in next_states(state): |
| 35 | if neighbor not in seen: |
| 36 | seen.add(neighbor) |
| 37 | queue.append((neighbor, steps + 1)) |
| 38 | Â |
| 39 | return -1 |
seen holds every dead end and every state ever pushed, so each state enters queue at most once, and queue pops states in non-decreasing order of steps.Write each configuration as one hashable state (here the 4-digit code) and run BFS on a graph that is never stored: pop a state, build each neighbor on the spot by turning one wheel one slot with (digit + move) % 10, and push every neighbor that is not in seen. Every move costs one step, so BFS pops states in order of steps, and the first time target comes off queue its steps is the fewest; putting the dead ends into seen before the search means no move can ever enter one. The trap is a partial key: seen must hold the whole state, here all four wheels, and (row, col, keys) or (row, col, removals_left) when a maze adds keys or wall removals. A later visit that differs only in the left-out part is a different state, and a key without that part skips it as already seen.
See it run
State-Space BFS on a lock, step by step
state 0000steps 0queue 1seen 2
Each column is one wheel. The first row is the popped state. The other rows are the states made by turning that wheel up or down by one slot.
pusheda new state, added to seen and to the queueseena state that seen already holdsdead enda state that may never be entered
Start: seen holds the dead ends "2000" and "0000". The queue holds ("0000", 0).
Gotcha 1 of 4
- The trap
Gotcha 1: Keying
seenon part of the stateMistakeif (nr, nc) not in seen: seen.add((nr, nc))Fixif (nr, nc, nrem) not in seen: seen.add((nr, nc, nrem))What happens:
seen.add(neighbor)must store the whole state. Here that is all four wheels. In Shortest Path in a Grid with Obstacles Elimination (LC 1293), the state is(row, col, removals_left). A later visit to the same cell with more removals left is a different state. Keyed on the cell alone,seenskips it, and the answer is lost.Example: Shortest Path in a Grid with Obstacles Elimination (LC 1293): grid = [[0,0],[1,1],[1,1],[1,0]], k = 2Mistake: returns -1Fix: returns 4
- Where you are is just a cell of a given grid, as in Shortest Path in Binary Matrix (LC 1091): the neighbours are read off the grid, and no state has to be encoded or built. See Shortest-Path BFS
- The states are still built on the spot, but only some moves count, as in Minimum Moves to Move a Box to Their Target Location (LC 1263), where walking is free and each push costs 1: BFS levels no longer equal the answer. See Zero-One BFS
Deep Dive
A state is everything that decides the moves ahead
Shortest-Path BFS already shows that the first pop of the goal is the fewest moves. This card changes only what a node is. A node is a state, and the graph is never stored. The code builds the neighbours of one state at the moment it pops it.
In Open the Lock (LC 752), the state is the four-digit text such as "0000". There are 10^4 = 10,000 states. Each wheel can turn up or down by one slot, so every state has 8 neighbours. The wheel wraps, so (digit + move) % 10 gives 0 after 9 and 9 before 0.
To choose the state, ask this question: if two situations have the same state, do they have the same moves and the same future? If not, a part of the situation is missing from the key.
Example: in Shortest Path in a Grid with Obstacles Elimination (LC 1293), the cell (row, col) is not enough. A visit with 2 removals left can go where a visit with 0 removals left cannot. The state is (row, col, removals_left). For grid = [[0,0],[1,1],[1,1],[1,0]] and k = 2, the full key returns 4 and the key (row, col) returns -1.
One trace: dead ends in seen, and a state that waits in the queue
The board replays openLock(["2000"], "1100"). The answer is 2. The first row is the popped state, and the next two rows are the 8 neighbours, two for each wheel.
seen starts with "2000", so no move can enter that dead end. Then the start "0000" is added. The pop of "0000" pushes 8 states with steps = 1, in this order: "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009".
The pop of "1000" builds "2000", which is a dead end, and "0000", which is in seen. It pushes 6 new states with steps = 2, and "1100" is the first of them.
Later, the pop of "0100" builds "1100" and "9100". Both states are still waiting in queue, but seen already holds them, so neither is pushed a second time. This is the first step marked as the trap on the board. The pops of "0900", "0010", "0090", "0001" and "0009" each repeat it with two more states.
After all 8 states with steps = 1 are popped, "1100" comes to the front. It equals target, so the function returns 2.
Dead ends and the start state
A dead end is a state that may never be entered. The blueprint puts the dead ends into seen before the search. A move to a dead end then fails the test neighbor not in seen, the same test that skips a visited state. No extra check is needed in the loop.
The start is different. The search adds "0000" to seen and to queue before the loop, so the loop never tests it. The guard if "0000" in seen: return -1 must run first. For deadends = ["0000"] and target = "8888", the right answer is -1. Without the guard, the search leaves the dead end and returns 8.
Example: for deadends = [] and target = "0000", the guard passes, the first pop equals target, and the answer is 0.
Wrapping needs % 10. Without it, turning 0 down builds the text "-1000". When that state is popped, int(state[i]) reads "-", and Python raises ValueError. In Java, C++ and C#, write (digit + move + 10) % 10, because -1 % 10 is -1 there.
The cost: states times work per state, and bidirectional search
The card's complexity line is O(B + V * T). V is the number of reachable states, T is the cost of one next_states call, and B is the cost of putting the blocked states into seen.
For openLock, W = 4 wheels. There are at most 10^W states. One state builds 2 * W neighbours, and each neighbour is a new text of W characters, so T = O(W^2). With D dead ends, the total is O(10^W * W^2 + D * W) time.
Example: for the LeetCode example with dead ends ["0201","0101","0102","1212","2002"] and target "0202", the answer is 6, and 822 states are popped. For deadends = [] and target = "5555", the answer is 20, and all 10,000 states are popped.
When the goal state is known and the moves can be undone, bidirectional BFS searches from both ends. It keeps one set of states from start and one from target. Each round it expands the smaller set. It stops when a new neighbor is in the other set. Each side goes about half the depth, so far fewer states are built. This is the method for Word Ladder (LC 127).
60-Second Pitch
"The lock has 10,000 states, and a move turns one wheel by one slot. So I treat each four-digit text as a node and build its 8 neighbours when I pop it, with (digit + move) % 10. I put the dead ends into seen first, so no move can enter one. I also check that "0000" is not a dead end, because the loop never tests the start. Every move costs one step, so BFS pops states in order of steps. The first pop of target is the fewest turns, and an empty queue means -1. The time is O(10^W * W^2 + D * W). If the goal is known, I can search from both ends and expand the smaller side."
Common Questions
- How do you decide what goes into the state?
Put in every value that changes which moves are possible or what the answer is later. Test it with two situations that have the same state: they must have the same future. In Shortest Path in a Grid with Obstacles Elimination (LC 1293), the cell is not enough, and
removals_leftmust be in the key.- Why are the dead ends put into
seenand not checked in the loop? The loop already skips every
neighborthat is inseen. A dead end is a state that may never be entered, which is the same rule for the loop. One set and one test cover both cases. The start needs its own check, because it is pushed before the loop.- What are the time and space complexity of
openLock? O(10^W * W^2 + D * W) time and O(10^W * W + D * W) space, where
Wis the number of wheels andDis the number of dead ends. There are at most 10^W states. Each builds 2 * W neighbours of W characters, andseenstores the states and the dead ends.- When is bidirectional BFS worth using, and how does it stop?
Use it when the goal state is known and a move can be undone, so the search can also start from
target. Keep one set of states from each end, and always expand the smaller set. Stop when a newneighboris in the other set. Add the steps of both sides for the answer.- What changes when the moves have different costs?
The first pop of
targetis then not always the cheapest. A path with more moves can cost less. For general positive costs, use a cheapest-first search with a heap, as in Network Delay Time (LC 743). Thestateidea stays the same.
SWE Reasoning
Spot it
- The question asks for the fewest moves between two configurations, such as a lock code, a word, a board or a pair of values.
- There is no grid or graph in the input. The code has to build the next configurations from the current one.
- Each move changes the configuration a little: one wheel, one letter, one tile.
- Every move costs the same, and some configurations are forbidden, such as dead ends.
- The number of configurations is limited, for example 10^4 lock codes, so a search over all of them is affordable.
The invariant, step by step
seenstarts with every dead end. If"0000"is inseen, the function returns -1.- Otherwise
"0000"is added toseen, andqueueholds("0000", 0). - The loop pops
(state, steps). Ifstate == target, it returnssteps. - It builds the 8 neighbours by turning one wheel one slot with
(digit + move) % 10. - A
neighborthat is not inseenis added toseenand pushed withsteps + 1. A dead end and a visited state are both inseen, so both are skipped. - Each state enters
queueat most once, and the pops come out in non-decreasing order ofsteps. The first pop oftargetis the fewest moves. Ifqueueempties first, the function returns -1.
Traps
- Key is a part of the state. In Shortest Path in a Grid with Obstacles Elimination (LC 1293), a key of
(row, col)skips a later visit with more removals left. For[[0,0],[1,1],[1,1],[1,0]]andk = 2, the answer is -1 instead of 4. Put every value that changes the future moves into the key. - Start in
seenis not checked. The loop never tests"0000". Fordeadends = ["0000"], the search returns 8 instead of -1 fortarget = "8888". - Missing
% 10. Turning 0 down builds"-1000", and the next pop raisesValueError. The same code with% 10returns 1 fortarget = "0009". - Mark at pop time. A state waits in
queuewithout being inseen, so other states push it again. Fortarget = "5555", marking at pop time with a skip for popped states makes 40,001 pushes, and marking at push time makes 10,000. - One-sided search with a known goal. In Word Ladder (LC 127), a search from the start alone builds every level to the full depth. Search from both ends and expand the smaller set.