How do you solve Open the Lock?

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.

Open the Lock

Q: What is the time complexity of Open the Lock?

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).

Q: What pattern does Open the Lock use?

The Pattern: BFS (Shortest Path on Unweighted Graph) The Heuristic: 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.

Medium BFS

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

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Output: 6

Starting 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use BFS starting from '0000'. Maintain a queue of (state, moves) pairs and a visited set…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

1class 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

To immediately return -1 if the initial state '0000' is a deadend, as no moves are possible.

Initialize BFS Queue and Visited Set with Starting State

To set up the BFS traversal starting from '0000' with zero moves made.

Perform BFS to Explore All Valid Next States

To iteratively dequeue states, check for the target, and enqueue all valid neighbors not in deadends or visited.

Return -1 if Target is Unreachable

To return -1 when BFS exhausts all reachable states without finding the target.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 14 Critical

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.

Line 5 Critical

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.

Line 15 Critical

return moves

Return the number of moves taken to reach the target.

This terminates the search with the minimal move count, guaranteed by BFS ordering.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does BFS guarantee that the first time the target state is dequeued corresponds to the minimum number of moves?

See the answer with Pro.

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

or drill a free problem

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`