Open the Lock
Problem
Given a list of deadend combinations and a target combination, return the minimum number of moves required to reach the target from '0000' by turning one wheel one digit at a time, avoiding deadends; return -1 if impossible.
- 1 ≤ deadends.length ≤ 500
- deadends[i].length == 4
- target.length == 4
- target will not be in deadends
- Each string consists of digits from '0' to '9'
Example
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6Starting from '0000', the BFS explores all valid states layer by layer. It avoids deadends by skipping them. The critical moment occurs when the algorithm reaches '0202' after 6 moves. The BFS guarantees this is the shortest path because it explores all states reachable in fewer moves first. The queue maintains states paired with their move counts, ensuring the first time the target is dequeued corresponds to the minimal moves.
Approach
Straightforward Solution
A brute-force approach might try all possible sequences of moves without pruning, leading to exponential time and repeated states. This is infeasible due to the large state space (10,000 possible states).
Core Observation
The lock's state space can be modeled as a graph where each node is a 4-digit string and edges connect states differing by one wheel turn. The shortest path in this unweighted graph corresponds to the minimum moves to reach the target.
Path to Optimal
Recognizing the problem as shortest path in an unweighted graph suggests BFS. BFS explores states in order of increasing distance from the start, guaranteeing the first time the target is found is the shortest path. Using a queue and a visited set prevents revisiting states and infinite loops. Deadends are treated as blocked nodes and skipped during exploration.
Optimal Approach
Use BFS starting from '0000'. Maintain a queue of (state, moves) pairs and a visited set. For each dequeued state, generate all neighbors by incrementing or decrementing each digit. Skip neighbors in deadends or already visited. When the target is dequeued, return the associated move count. If the queue empties without finding the target, return -1.
Time
O(10^4)
The state space consists of 10,000 possible lock combinations (0000 to 9999). Each state generates up to 8 neighbors (4 wheels × 2 directions). BFS visits each state at most once, so the total operations are bounded by O(10^4).
Space
O(10^4)
The visited set and queue can hold up to all possible states in the worst case, resulting in O(10^4) auxiliary space. This is necessary to avoid revisiting states and infinite loops.
Pattern Spotlight
BFS (Shortest Path on Unweighted Graph)
When a problem asks for the minimum number of moves or steps in a state space where each move has equal cost, model the problem as a graph and use BFS to explore states layer by layer, ensuring the first time the target is reached corresponds to the shortest path.
Solution
| 1 | class Solution: |
| 2 | def openLock(self, deadends: List[str], target: str) -> int: |
| 3 | dead = set(deadends) |
| 4 | |
| 5 | if "0000" in dead: |
| 6 | return -1 |
| 7 | |
| 8 | q = deque([("0000", 0)]) |
| 9 | seen = {"0000"} |
| 10 | |
| 11 | while q: |
| 12 | state, moves = q.popleft() |
| 13 | |
| 14 | if state == target: |
| 15 | return moves |
| 16 | |
| 17 | for i in range(4): |
| 18 | digit = int(state[i]) |
| 19 | |
| 20 | for step in (-1, 1): |
| 21 | new_digit = (digit + step) % 10 |
| 22 | next_state = state[:i] + str(new_digit) + state[i+1:] |
| 23 | |
| 24 | if next_state not in dead and next_state not in seen: |
| 25 | seen.add(next_state) |
| 26 | q.append((next_state, moves + 1)) |
| 27 | |
| 28 | return -1 |
Step-by-Step Solution
Convert Deadends to a Set for O(1) Lookup
| 3 | dead = set(deadends) |
Objective
To efficiently check if a state is a deadend by storing deadends in a hash set.
Key Insight
Deadends represent forbidden states that must be avoided. Using a set allows constant-time membership checks, which is critical for pruning the BFS search space efficiently. Without this, checking deadends would be O(n) per state, drastically increasing runtime.
Interview Quick-Check
Core Logic
Using a set for deadends enables O(1) membership checks, which is essential for pruning invalid states during BFS.
Common Pitfalls & Bugs
Failing to convert deadends to a set leads to inefficient lookups and potential timeouts.
Handle Immediate Deadend Starting State
| 5 | if "0000" in dead: |
| 6 | return -1 |
Objective
To immediately return -1 if the initial state '0000' is a deadend, as no moves are possible.
Key Insight
If the starting state is blocked, no exploration is possible. Detecting this early prevents unnecessary computation and correctly returns the failure case.
Interview Quick-Check
State & Boundaries
Check if '0000' is in deadends before starting BFS to handle trivial no-solution cases.
Initialize BFS Queue and Visited Set with Starting State
| 8 | q = deque([("0000", 0)]) |
| 9 | seen = {"0000"} |
Objective
To set up the BFS traversal starting from '0000' with zero moves made.
Key Insight
The queue stores states paired with the number of moves taken to reach them, enabling BFS to track distance from the start. The visited set prevents revisiting states, avoiding infinite loops and redundant work.
Interview Quick-Check
Core Logic
The queue holds tuples of (state, moves) to track BFS layers and distances.
State & Boundaries
The visited set ensures each state is processed only once, maintaining BFS correctness and efficiency.
Perform BFS to Explore All Valid Next States
| 11 | while q: |
| 12 | state, moves = q.popleft() |
| 14 | if state == target: |
| 15 | return moves |
| 17 | for i in range(4): |
| 18 | digit = int(state[i]) |
| 20 | for step in (-1, 1): |
| 21 | new_digit = (digit + step) % 10 |
| 22 | next_state = state[:i] + str(new_digit) + state[i+1:] |
| 24 | if next_state not in dead and next_state not in seen: |
| 25 | seen.add(next_state) |
| 26 | q.append((next_state, moves + 1)) |
Objective
To iteratively dequeue states, check for the target, and enqueue all valid neighbors not in deadends or visited.
Key Insight
BFS explores the state space layer by layer. For each state, generating neighbors by incrementing or decrementing each wheel digit covers all possible one-move transitions. Skipping deadends and visited states prunes the search space. Returning immediately upon reaching the target guarantees minimal moves.
Interview Quick-Check
Core Logic
BFS explores states in order of increasing moves, generating neighbors by changing each digit up or down with wrap-around.
State & Boundaries
The loop continues until the queue is empty or the target is found, ensuring exhaustive search of reachable states.
Common Pitfalls & Bugs
Forgetting to mark neighbors as visited before enqueueing can cause duplicate processing and inefficiency.
Complexity
Each state is enqueued at most once, bounding the BFS runtime to the size of the state space.
Return -1 if Target is Unreachable
| 28 | return -1 |
Objective
To return -1 when BFS exhausts all reachable states without finding the target.
Key Insight
If the queue empties without dequeuing the target, it means the target is unreachable due to deadends or disconnected state space. Returning -1 signals failure to the caller.
Interview Quick-Check
State & Boundaries
Return -1 only after all reachable states have been explored and the target was not found.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if state == target:Check if the current state matches the target.
Finding the target means the shortest path has been found, so the algorithm can return immediately.
if "0000" in dead:Check if the initial state '0000' is a deadend.
If the start state is blocked, no moves are possible, so the function must return -1 immediately to avoid unnecessary computation.
return movesReturn the number of moves taken to reach the target.
This terminates the search with the minimal move count, guaranteed by BFS ordering.
if next_state not in dead and next_state not in seen:Check if the new state is neither a deadend nor visited.
Pruning deadends and already visited states prevents invalid or redundant exploration, ensuring BFS efficiency and correctness.
dead = set(deadends)Convert deadends list into a set for fast membership checking.
Using a set enables O(1) average-time lookups to quickly determine if a state is forbidden, which is critical for pruning during BFS.
q = deque([("0000", 0)])Initialize the BFS queue with the starting state and zero moves.
The queue stores states paired with their distance from the start, enabling BFS to explore states in order of increasing moves.
seen = {"0000"}Initialize the visited set with the starting state.
Tracking visited states prevents revisiting and infinite loops, ensuring BFS explores each state only once.
state, moves = q.popleft()Dequeue the next state and its move count.
FIFO ordering ensures states are explored in order of increasing moves, which is essential for BFS correctness.
seen.add(next_state)Mark the new state as visited.
Adding to visited before enqueueing prevents duplicate entries and infinite loops.
q.append((next_state, moves + 1))Enqueue the new state with incremented move count.
Scheduling the neighbor for future exploration maintains BFS layer-by-layer traversal and tracks distance.
return -1Return -1 when the start state is a deadend.
This early return handles an edge case that prevents BFS from running on an impossible problem.
while q:Begin BFS loop while there are states to explore.
The loop processes states layer by layer, guaranteeing shortest path discovery in an unweighted graph.
new_digit = (digit + step) % 10Calculate the new digit after turning the wheel with wrap-around.
Using modulo 10 ensures digits wrap from 9 to 0 and vice versa, maintaining valid lock states.
next_state = state[:i] + str(new_digit) + state[i+1:]Construct the new lock state string after the wheel turn.
Creating the new state string enables BFS to track and explore this neighbor state.
return -1Return -1 if the target is unreachable after exploring all states.
Exhausting the queue without finding the target means no valid path exists, so returning -1 correctly signals failure.
for i in range(4):Iterate over each wheel position in the lock state.
Each wheel can be turned independently, so exploring all positions is necessary to generate all possible next states.
for step in (-1, 1):Iterate over the two possible wheel turns: decrement and increment.
Each wheel can be turned one step forward or backward, generating two neighbors per wheel position.
digit = int(state[i])Extract the digit at the current wheel position.
Knowing the current digit allows calculation of the next possible digits by incrementing or decrementing.
Test Your Understanding
Why does BFS guarantee that the first time the target state is dequeued corresponds to the minimum number of moves?
Because BFS explores states in order of increasing distance from the start, it visits all states reachable in k moves before any states reachable in k+1 moves. Therefore, the first time the target is dequeued, it must be via the shortest path.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Open the Lock from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Open the Lock drill