← DSA Atlas
Dedicated problem page · #752

Open the Lock

MediumGraph DFS and BFSShortest path over a state graphBFS
Solve on LeetCode ↗
752
MediumGraph DFS and BFSBFSShortest path over a state graph

Open the Lock

A 4-wheel combination lock starts at '0000'. Each move rotates one wheel one notch up or down (9 wraps to 0 and 0 wraps to 9). A list of deadends are configurations the lock can never show. Return the minimum number of single-wheel turns to reach the target, or -1 if it is impossible.

Open official problem prompt ↗
In plain English

Find the least number of single-notch wheel turns transforming '0000' into a target combination without ever passing through a forbidden state.

Picture it like this

Think of ripples spreading on a pond: BFS touches every combination exactly one turn away, then every combination two turns away, and so on. The instant the ripple reaches the target you know the exact distance.

Example
Input
deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output
6
Why
A valid shortest sequence is 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202, which takes 6 turns while avoiding every deadend.
Constraints
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target is not in deadendstarget and deadends[i] consist of digits only
Pattern lesson

See the pattern, then code

Shortest path over a state graph
Recognition clue

Every move has uniform cost (one turn) and you want the fewest moves between two configurations, over a finite state space of 10^4 combinations. Uniform-cost shortest path on an implicit graph is classic BFS.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Treat each 4-digit string as a node with 8 neighbors (turn each of 4 wheels up or down). BFS explores states in increasing distance from '0000', so the first time target is dequeued the step count is minimal. Deadends and visited states are simply never enqueued.

New words, made simpleKnow these before the algorithm
State
One full 4-digit lock configuration, e.g. '0250'.
Neighbor
A state reachable in one turn — turn any single wheel up or down.
Deadend
A state that is off-limits and must never be entered.
BFS layer
All states at the same turn-distance from the start.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
DFS / brute-force enumeration

Cannot guarantee minimum turns and blows up on cycles; wrong tool for uniform shortest path.

Recursively try wheel turns and track the shortest completion found.

Time Exponential without memo; revisits states endlesslySpace O(depth)
Best choiceBFS over the state graph

First arrival at target is provably the fewest turns; visited set keeps it linear.

Layer-by-layer exploration from '0000', enqueuing each unvisited, non-deadend neighbor.

Time O(N) over at most 10^4 states, 8 edges eachSpace O(N)
The rule we keep true

Invariant

When a state is dequeued, steps stored with it equals the minimum number of turns from '0000' to that state.

Why this is correct

Reasoning

BFS dequeues states in non-decreasing distance order and each state is enqueued only once (guarded by the visited set). Since every edge costs exactly one turn, the level at which target is first reached is its shortest distance; if the queue empties without reaching it, no legal path exists.

The algorithm in three movesSay these aloud before coding
1Return -1 immediately if '0000' is a deadend; return 0 if target is '0000'

queue front = ('0000', 0)

2Seed a queue with ('0000', 0) and a visited set containing '0000'

visited grows outward one ring per level

3Pop a state; for each of 4 wheels generate the +1 and -1 neighbor with modulo-10 wrap

target '0202' first dequeued at depth 6

4Skip neighbors that are deadends or already visited; otherwise enqueue with steps+1

5Return the step count when target is reached, else -1 when the queue empties

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00000
10001
11002
12003
12014
12025
02026
1 · Readstart '0000'
2 · AskIs start a deadend or already the target?
3 · Update statequeue=[('0000',0)], seen={'0000'}
4 · ResultNeither; begin BFS.
Key takeaway

One shortest 6-turn walk through the lock's state graph from 0000 to 0202.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-8Guard clauses

    If the start itself is forbidden there is no path; if target is the start the answer is trivially 0 turns.

  2. 2
    Lines 9-10Queue and visited seeding

    The visited set doubles as a dedup filter so no state is ever expanded twice.

  3. 3
    Lines 14-22Neighbor generation

    For each wheel, (d+1)%10 and (d-1)%10 handle the 0/9 wraparound; string splicing builds the next state, rejected if dead or seen.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • '0000' is itself a deadend -> return -1
  • target == '0000' -> return 0 before any BFS
  • target is unreachable because deadends wall it off -> return -1
  • deadends is empty -> pure BFS over full space
!

Common beginner mistakes

  • Forgetting the modulo wrap so wheel 0 fails to reach 9 and vice versa
  • Adding the start to the queue but not to visited, allowing it to be re-expanded
  • Checking the deadend condition only on the start and not on generated neighbors
  • Marking visited at dequeue time instead of enqueue time, which can enqueue the same state many times
Check your understanding

Why is it safe to mark a state visited the moment it is enqueued rather than when it is dequeued?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#133Clone GraphGraph traversal with clone map#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill