Open the Lock (LeetCode 752)
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.
Worked Examples
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6deadends = ["8888"], target = "0009"1deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"-1⚖️Formal Constraints & Bounds
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target will not be in the list
deadends.targetanddeadends[i]consist of digits only.
Core Insight
Each code is a state with 8 neighbours built on the spot; the dead ends go into seen before the search, every other state is marked when it is pushed, and the first pop of target gives the fewest turns.
Real-World Scenario & Production Applications
Combination-lock / PIN-recovery minimum-turn puzzles and finite-state device configuration search where each 'wheel' is an independent setting with wraparound.
Subproblems & Recurrence Decomposition3 Phases
A dead end may never be entered, so put every one into seen before the search. If "0000" is itself a dead end, no move is possible: return -1.
seen = set(deadends)
if "0000" in seen:
return -1Step-by-Step Execution Trace Table
Example 1, deadends = ["0201","0101","0102","1212","2002"], target = "0202". Neighbours are built wheel by wheel, up before down.
| Pop # | state (steps) | Neighbours built | Skipped: already in seen | Pushed with steps + 1 |
|---|---|---|---|---|
| 1 | "0000" (0) | 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009 | none | all 8 |
| 2 | "1000" (1) | 2000, 0000, 1100, 1900, 1010, 1090, 1001, 1009 | 0000 (popped) | 7, including 1100 |
| 3 | "9000" (1) | 0000, 8000, 9100, 9900, 9010, 9090, 9001, 9009 | 0000 | 7 |
| 4 | "0100" (1) | 1100, 9100, 0200, 0000, 0110, 0190, 0101, 0109 | 1100 and 9100 (already queued: marked when pushed), 0000, 0101 (dead end) | 0200, 0110, 0190, 0109 |
| ... | levels 1 to 5 | ... | ... | 8, 31, 86, 190 and 356 codes are popped at 1, 2, 3, 4 and 5 turns |
| 822 | "0202" (6) | not needed | state == target: return 6 |
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6Example 1, deadends = ["0201","0101","0102","1212","2002"], target = "0202". Neighbours are built wheel by wheel, up before down.
| Pop # | state (steps) | Neighbours built | Skipped: already in seen | Pushed with steps + 1 |
|---|---|---|---|---|
| 1 | "0000" (0) | 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009 | none | all 8 |
| 2 | "1000" (1) | 2000, 0000, 1100, 1900, 1010, 1090, 1001, 1009 | 0000 (popped) | 7, including 1100 |
| 3 | "9000" (1) | 0000, 8000, 9100, 9900, 9010, 9090, 9001, 9009 | 0000 | 7 |
| 4 | "0100" (1) | 1100, 9100, 0200, 0000, 0110, 0190, 0101, 0109 | 1100 and 9100 (already queued: marked when pushed), 0000, 0101 (dead end) | 0200, 0110, 0190, 0109 |
| ... | levels 1 to 5 | ... | ... | 8, 31, 86, 190 and 356 codes are popped at 1, 2, 3, 4 and 5 turns |
| 822 | "0202" (6) | not needed | state == target: return 6 |
| 1 | seen = set(deadends) |
| 2 | if '0000' in seen: |
| 3 | return -1 |
| 4 | seen.add('0000') |
| 5 | queue = deque([('0000', 0)]) |
| 6 | while queue: |
| 7 | state, steps = queue.popleft() |
| 8 | if state == target: |
| 9 | return steps |
| 10 | for i in range(4): |
| 11 | for move in (1, -1): |
| 12 | neighbor = state with wheel i turned to (digit + move) % 10 |
| 13 | if neighbor not in seen: |
| 14 | seen.add(neighbor) |
| 15 | queue.append((neighbor, steps + 1)) |
| 16 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Open the Lock is shortest-path BFS on a graph that is never written down. Each 4-digit code the lock can show is a state, and one turn of one wheel is an edge of cost 1. There are 10,000 codes and each has exactly 8 neighbours (4 wheels, each up or down), but nobody stores those edges: openLock builds the neighbours of a state only when that state comes off the queue.
🏟️ The Analogy: A Maze of 10,000 Rooms
Picture a maze with one room per code, 0000 to 9999. You start in room 0000, and every room has 8 doors: turn one of the 4 wheels up or down. From 0000 the doors lead to 1000 and 9000, 0100 and 0900, 0010 and 0090, 0001 and 0009. The dead ends are rooms full of lava: you may never step in, so they go into seen before the search starts, as if already visited. BFS walks the maze ring by ring: first every room one turn away, then every room two turns away, until it opens the target's door.
🔑 The Key Idea in the Code
(digit + move) % 10 is the wheel: Python's % always returns a value from 0 to 9 here, so (0 - 1) % 10 is 9 and (9 + 1) % 10 is 0, with no if for the ends. And seen.add(neighbor) sits next to queue.append, not after popleft: "1100" is one turn from both "1000" and "0100", and marking it only when it is popped would push it twice. With 8 neighbours per state, the queue fills with copies of the same codes.
Keying
seenon part of the stateNot checking whether
"0000"is a dead endBuilding the next digit without
% 10Searching from one side when the goal is known
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for the smallest number of moves, and one move turns a single wheel by one position: fewest moves when every move costs the same means BFS. But there is no grid and no edge list. Where the lock is, is the whole 4-digit code, and the codes one move away have to be built from it. That is State-Space BFS: BFS over states you generate yourself, with the jamming codes as states you may never enter.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision rule (the card's invariant keeps it correct): push a neighbor only when neighbor not in seen, calling seen.add(neighbor) in the same step, and return steps the first time state == target after popleft.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A partial key:
seen.add(neighbor)stores the whole code, all four wheels. Keyed on the first three wheels only,"0001"and"0009"look like the already-seen"0000"and are never pushed, so Example 2 (target = "0009") returns -1 instead of 1.Marking on pop:
seen.add(neighbor)must run together withqueue.append, not afterpopleft."1100"is one turn from both"1000"and"0100", and marking on pop pushes it once for each of them.Testing the target at the wrong moment: return
stepswhentargetis popped, orsteps + 1when a pushedneighboris the target; mixing the two is off by one. The pop-time test also coverstarget == "0000", whose answer is0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use State-Space BFS. Every code is a state and one turn is a move of cost one: a shortest path on a graph of ten thousand codes I never build. I put the dead ends into seen first, and return minus one at once if zero-zero-zero-zero is dead. Then I pop a state, return its steps if it is the target, and otherwise build its eight neighbours: each wheel up or down, mod ten so it wraps. I push a neighbour only if it is not in seen, and mark it in that same step. The trap is keying seen on less than the whole state: two codes that share three wheels are still different states, just as a maze cell visited with more keys is a new state. BFS pops in order of steps, so the first pop of the target is the answer. With W wheels and D dead ends: O(10 to the W, times W squared, plus D times W) time, and O(10 to the W, times W, plus D times W) space."
Complexity & Mathematical Proof
O(10^W * W^2 + D * W)
Look at the code: seen = set(deadends) hashes D strings of W digits, O(D * W). seen.add(neighbor) runs together with queue.append, so each of the at most 10^W codes is pushed once and popped once. Each pop runs for i in range(len(state)) (W wheels) times for move in (1, -1) (2 moves): 2W neighbours, and each neighbor = state[:i] + str((digit + move) % 10) + state[i + 1:] builds and hashes a W-character string in O(W). So one pop costs O(W^2), and all pops together O(10^W * W^2).
O(10^W * W + D * W)
Look at what is alive at once: seen holds the D dead ends plus every pushed code, at most 10^W of them, each a W-character string; queue holds at most 10^W (state, steps) pairs. There is no recursion, and the answer is one integer.
T = D * W (dead ends into seen) + 10^W pops x 2W neighbours x O(W) per neighbour = O(10^W * W^2 + D * W)
Derivation Progression
set(deadends): D strings x O(W)
Hashing each dead end reads its W digits.
at most 10^W codes, each pushed and popped once
seen.add(neighbor) runs together with queue.append, so no code is pushed twice.
for i in range(len(state)) x for move in (1, -1): 2W
Each wheel is turned one slot up and one slot down.
state[:i] + str((digit + move) % 10) + state[i + 1:] and the seen lookup: O(W)
Building and hashing a W-character string.
D * W + 10^W x 2W x O(W) = O(10^W * W^2 + D * W)
With W = 4 that is at most 10,000 pops and 80,000 neighbours built.
Variable Definitions
len(state), the number of wheels (4 here, so 10^W = 10,000 codes)
len(deadends), the number of dead ends (1 to 500)
Memory Architecture & Bounds
O(1): no recursion
O(10^W * W + D * W): seen (dead ends plus pushed codes) and queue
O(1): one integer
Boundary Best / Worst Cases
: "0000" is a dead end, or target is "0000"
: target can't be reached, so every reachable code is popped (Example 3 pops 9,991 codes)
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "smallest number of moves", "one move turns a single wheel by one position", "codes that jam the lock". Fewest moves at equal cost, but the position is a whole 4-digit code, not a cell of a grid: State-Space BFS over states generated on the spot, with the dead ends as states you may never enter.
wheels, so at most codes with neighbours each, and up to dead ends: the whole space fits in memory. At scale it stops fitting: with there are codes, and a set of strings is too big for one process. Encode each code as an integer (a -bit bitmap is 12.5 MB) or search from both ends at once.
Queue memory is the first thing to run out at scale: every duplicate push is a queue slot, which is why marking on push matters more here than the time it saves. When the space is too large even with compact states, search from both ends (bidirectional BFS) so each side only goes about half the depth.
Core Algorithmic State Invariants
stepsTravels With Each State
Pushing (neighbor, steps + 1) gives every popped code its own distance, so no level-by-level loop is needed. Counting rounds with level_size, as in Level-Order BFS, gives the same answer; the tuple just keeps the loop flat.
Open the Lock (LeetCode 752)
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.
Worked Examples
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6deadends = ["8888"], target = "0009"1deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"-1⚖️Formal Constraints & Bounds
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target will not be in the list
deadends.targetanddeadends[i]consist of digits only.
Core Insight
Each code is a state with 8 neighbours built on the spot; the dead ends go into seen before the search, every other state is marked when it is pushed, and the first pop of target gives the fewest turns.
Real-World Scenario & Production Applications
Combination-lock / PIN-recovery minimum-turn puzzles and finite-state device configuration search where each 'wheel' is an independent setting with wraparound.
Subproblems & Recurrence Decomposition3 Phases
A dead end may never be entered, so put every one into seen before the search. If "0000" is itself a dead end, no move is possible: return -1.
seen = set(deadends)
if "0000" in seen:
return -1Step-by-Step Execution Trace Table
Example 1, deadends = ["0201","0101","0102","1212","2002"], target = "0202". Neighbours are built wheel by wheel, up before down.
| Pop # | state (steps) | Neighbours built | Skipped: already in seen | Pushed with steps + 1 |
|---|---|---|---|---|
| 1 | "0000" (0) | 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009 | none | all 8 |
| 2 | "1000" (1) | 2000, 0000, 1100, 1900, 1010, 1090, 1001, 1009 | 0000 (popped) | 7, including 1100 |
| 3 | "9000" (1) | 0000, 8000, 9100, 9900, 9010, 9090, 9001, 9009 | 0000 | 7 |
| 4 | "0100" (1) | 1100, 9100, 0200, 0000, 0110, 0190, 0101, 0109 | 1100 and 9100 (already queued: marked when pushed), 0000, 0101 (dead end) | 0200, 0110, 0190, 0109 |
| ... | levels 1 to 5 | ... | ... | 8, 31, 86, 190 and 356 codes are popped at 1, 2, 3, 4 and 5 turns |
| 822 | "0202" (6) | not needed | state == target: return 6 |
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6Example 1, deadends = ["0201","0101","0102","1212","2002"], target = "0202". Neighbours are built wheel by wheel, up before down.
| Pop # | state (steps) | Neighbours built | Skipped: already in seen | Pushed with steps + 1 |
|---|---|---|---|---|
| 1 | "0000" (0) | 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009 | none | all 8 |
| 2 | "1000" (1) | 2000, 0000, 1100, 1900, 1010, 1090, 1001, 1009 | 0000 (popped) | 7, including 1100 |
| 3 | "9000" (1) | 0000, 8000, 9100, 9900, 9010, 9090, 9001, 9009 | 0000 | 7 |
| 4 | "0100" (1) | 1100, 9100, 0200, 0000, 0110, 0190, 0101, 0109 | 1100 and 9100 (already queued: marked when pushed), 0000, 0101 (dead end) | 0200, 0110, 0190, 0109 |
| ... | levels 1 to 5 | ... | ... | 8, 31, 86, 190 and 356 codes are popped at 1, 2, 3, 4 and 5 turns |
| 822 | "0202" (6) | not needed | state == target: return 6 |
| 1 | seen = set(deadends) |
| 2 | if '0000' in seen: |
| 3 | return -1 |
| 4 | seen.add('0000') |
| 5 | queue = deque([('0000', 0)]) |
| 6 | while queue: |
| 7 | state, steps = queue.popleft() |
| 8 | if state == target: |
| 9 | return steps |
| 10 | for i in range(4): |
| 11 | for move in (1, -1): |
| 12 | neighbor = state with wheel i turned to (digit + move) % 10 |
| 13 | if neighbor not in seen: |
| 14 | seen.add(neighbor) |
| 15 | queue.append((neighbor, steps + 1)) |
| 16 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Open the Lock is shortest-path BFS on a graph that is never written down. Each 4-digit code the lock can show is a state, and one turn of one wheel is an edge of cost 1. There are 10,000 codes and each has exactly 8 neighbours (4 wheels, each up or down), but nobody stores those edges: openLock builds the neighbours of a state only when that state comes off the queue.
🏟️ The Analogy: A Maze of 10,000 Rooms
Picture a maze with one room per code, 0000 to 9999. You start in room 0000, and every room has 8 doors: turn one of the 4 wheels up or down. From 0000 the doors lead to 1000 and 9000, 0100 and 0900, 0010 and 0090, 0001 and 0009. The dead ends are rooms full of lava: you may never step in, so they go into seen before the search starts, as if already visited. BFS walks the maze ring by ring: first every room one turn away, then every room two turns away, until it opens the target's door.
🔑 The Key Idea in the Code
(digit + move) % 10 is the wheel: Python's % always returns a value from 0 to 9 here, so (0 - 1) % 10 is 9 and (9 + 1) % 10 is 0, with no if for the ends. And seen.add(neighbor) sits next to queue.append, not after popleft: "1100" is one turn from both "1000" and "0100", and marking it only when it is popped would push it twice. With 8 neighbours per state, the queue fills with copies of the same codes.
Keying
seenon part of the stateNot checking whether
"0000"is a dead endBuilding the next digit without
% 10Searching from one side when the goal is known
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for the smallest number of moves, and one move turns a single wheel by one position: fewest moves when every move costs the same means BFS. But there is no grid and no edge list. Where the lock is, is the whole 4-digit code, and the codes one move away have to be built from it. That is State-Space BFS: BFS over states you generate yourself, with the jamming codes as states you may never enter.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision rule (the card's invariant keeps it correct): push a neighbor only when neighbor not in seen, calling seen.add(neighbor) in the same step, and return steps the first time state == target after popleft.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A partial key:
seen.add(neighbor)stores the whole code, all four wheels. Keyed on the first three wheels only,"0001"and"0009"look like the already-seen"0000"and are never pushed, so Example 2 (target = "0009") returns -1 instead of 1.Marking on pop:
seen.add(neighbor)must run together withqueue.append, not afterpopleft."1100"is one turn from both"1000"and"0100", and marking on pop pushes it once for each of them.Testing the target at the wrong moment: return
stepswhentargetis popped, orsteps + 1when a pushedneighboris the target; mixing the two is off by one. The pop-time test also coverstarget == "0000", whose answer is0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use State-Space BFS. Every code is a state and one turn is a move of cost one: a shortest path on a graph of ten thousand codes I never build. I put the dead ends into seen first, and return minus one at once if zero-zero-zero-zero is dead. Then I pop a state, return its steps if it is the target, and otherwise build its eight neighbours: each wheel up or down, mod ten so it wraps. I push a neighbour only if it is not in seen, and mark it in that same step. The trap is keying seen on less than the whole state: two codes that share three wheels are still different states, just as a maze cell visited with more keys is a new state. BFS pops in order of steps, so the first pop of the target is the answer. With W wheels and D dead ends: O(10 to the W, times W squared, plus D times W) time, and O(10 to the W, times W, plus D times W) space."
Complexity & Mathematical Proof
O(10^W * W^2 + D * W)
Look at the code: seen = set(deadends) hashes D strings of W digits, O(D * W). seen.add(neighbor) runs together with queue.append, so each of the at most 10^W codes is pushed once and popped once. Each pop runs for i in range(len(state)) (W wheels) times for move in (1, -1) (2 moves): 2W neighbours, and each neighbor = state[:i] + str((digit + move) % 10) + state[i + 1:] builds and hashes a W-character string in O(W). So one pop costs O(W^2), and all pops together O(10^W * W^2).
O(10^W * W + D * W)
Look at what is alive at once: seen holds the D dead ends plus every pushed code, at most 10^W of them, each a W-character string; queue holds at most 10^W (state, steps) pairs. There is no recursion, and the answer is one integer.
T = D * W (dead ends into seen) + 10^W pops x 2W neighbours x O(W) per neighbour = O(10^W * W^2 + D * W)
Derivation Progression
set(deadends): D strings x O(W)
Hashing each dead end reads its W digits.
at most 10^W codes, each pushed and popped once
seen.add(neighbor) runs together with queue.append, so no code is pushed twice.
for i in range(len(state)) x for move in (1, -1): 2W
Each wheel is turned one slot up and one slot down.
state[:i] + str((digit + move) % 10) + state[i + 1:] and the seen lookup: O(W)
Building and hashing a W-character string.
D * W + 10^W x 2W x O(W) = O(10^W * W^2 + D * W)
With W = 4 that is at most 10,000 pops and 80,000 neighbours built.
Variable Definitions
len(state), the number of wheels (4 here, so 10^W = 10,000 codes)
len(deadends), the number of dead ends (1 to 500)
Memory Architecture & Bounds
O(1): no recursion
O(10^W * W + D * W): seen (dead ends plus pushed codes) and queue
O(1): one integer
Boundary Best / Worst Cases
: "0000" is a dead end, or target is "0000"
: target can't be reached, so every reachable code is popped (Example 3 pops 9,991 codes)
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "smallest number of moves", "one move turns a single wheel by one position", "codes that jam the lock". Fewest moves at equal cost, but the position is a whole 4-digit code, not a cell of a grid: State-Space BFS over states generated on the spot, with the dead ends as states you may never enter.
wheels, so at most codes with neighbours each, and up to dead ends: the whole space fits in memory. At scale it stops fitting: with there are codes, and a set of strings is too big for one process. Encode each code as an integer (a -bit bitmap is 12.5 MB) or search from both ends at once.
Queue memory is the first thing to run out at scale: every duplicate push is a queue slot, which is why marking on push matters more here than the time it saves. When the space is too large even with compact states, search from both ends (bidirectional BFS) so each side only goes about half the depth.
Core Algorithmic State Invariants
stepsTravels With Each State
Pushing (neighbor, steps + 1) gives every popped code its own distance, so no level-by-level loop is needed. Counting rounds with level_size, as in Level-Order BFS, gives the same answer; the tuple just keeps the loop flat.