Open the Lock — BFS on State Space

Problem Statement

LeetCode 752 — Open the Lock (Medium)

A lock has 4 circular wheels, each with digits 0–9. The lock starts at "0000". You can rotate any single wheel up or down by one digit per turn (wrapping: 0→9 and 9→0). Certain combinations are deadends — if you reach them, the lock jams.

Return the minimum number of turns to reach the target combination from "0000", avoiding all deadends. Return -1 if it is impossible.

Constraints:

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target is not in deadends
target != "0000"

Example 1:

deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
 
Output: 6
Explanation: One optimal path:
  "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"
  6 turns total, avoiding all deadends.

Example 2:

deadends = ["8888"]
target = "0009"
 
Output: 1
Explanation: Rotate wheel 3 down once: "0000" → "0009". 1 turn.

Example 3:

deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"]
target = "8888"
 
Output: -1
Explanation: Every path to "8888" goes through a deadend. Impossible.

Why This Problem Matters

Open the Lock is a canonical state-space BFS problem. The lock combination "0000" through "9999" defines a graph of 10,000 nodes. From each node, there are exactly 8 edges (each of 4 wheels can move up or down). Deadend nodes are simply removed from the graph.

Interviewers use this problem to test:

State abstraction: Can you model a lock combination as a graph node?
Neighbor generation: Can you correctly generate all 8 adjacent states with circular wrapping?
Early termination: Can you stop BFS the moment you dequeue the target, rather than exploring the entire graph?
Edge-case awareness: What if "0000" is a deadend? What if target == "0000"?

The mental model — treat each configuration of a system as a node in a graph, and each valid transition as an edge — is fundamental. It unlocks Word Ladder, Sliding Puzzle, Rubik's Cube problems, and more.

The Core Insight

Model the problem as a shortest-path problem on an implicit graph:

Node: a 4-character string like "1234"
Edges: 8 neighbors (each wheel ±1, with wraparound)
Source: "0000"
Target: the given target string
Forbidden nodes: deadends

BFS from "0000" explores this graph level by level. The first time the target is reached, the number of levels traversed equals the minimum number of turns.

Circular arithmetic for wheel digit d:

Up: (d + 1) % 10
Down: (d - 1 + 10) % 10

The +10 before % 10 prevents negative modulo issues.

Visual Dry Run

Start: "0000", target: "0009", deadends: ["8888"]
 
Level 0: {"0000"}
Level 1 (1 turn from "0000"):
  Wheel 0 up  → "1000"
  Wheel 0 down→ "9000"
  Wheel 1 up  → "0100"
  Wheel 1 down→ "0900"
  Wheel 2 up  → "0010"
  Wheel 2 down→ "0090"
  Wheel 3 up  → "0001"
  Wheel 3 down→ "0009" ← matches target!
 
Return 1.

The simplicity of this example shows why BFS is optimal — it finds the shortest path by exploring outward in rings.

Common Mistakes

Not checking if "0000" is in deadends. If "0000" is a deadend, we can never even start. Return -1 immediately.
Not checking if target == "0000". The problem says target != "0000", but if a variant allows it, return 0 without any BFS.
Incorrect circular wrapping. (digit - 1) % 10 in Python gives -1 when digit == 0, not 9. Always use (digit - 1 + 10) % 10.
Adding deadends to visited set but still enqueuing them once. The safe approach: add all deadends to the visited set before BFS starts. Then deadend states will never be enqueued.
Generating neighbors as integers instead of strings. If you work with strings throughout, the code is cleaner and avoids leading-zero issues (e.g., int 9 vs string "0009").
Marking states visited on dequeue rather than enqueue. A state should be marked visited when it is first added to the queue. Marking on dequeue allows the same state to be enqueued multiple times from different parents, wasting time.

Solutions

Python

from collections import deque
 
class Solution:
    def openLock(self, deadends: list[str], target: str) -> int:
        dead = set(deadends)          # O(1) lookup for deadends
 
        # If the start state is a deadend, we can't move at all
        if '0000' in dead:
            return -1
 
        # Edge case: already at target
        if target == '0000':
            return 0
 
        visited = {'0000'}            # track visited states to avoid revisiting
        q = deque([('0000', 0)])      # queue of (state, turns_taken)
 
        while q:
            state, turns = q.popleft()  # expand current state
 
            # Generate all 8 neighbors (4 wheels × 2 directions)
            for i in range(4):
                for delta in (1, -1):
                    # Rotate wheel i by delta, with circular wraparound
                    new_digit = (int(state[i]) + delta) % 10
                    # Build new state string with this wheel changed
                    new_state = state[:i] + str(new_digit) + state[i+1:]
 
                    # Found the target
                    if new_state == target:
                        return turns + 1
 
                    # Enqueue if not visited and not a deadend
                    if new_state not in visited and new_state not in dead:
                        visited.add(new_state)
                        q.append((new_state, turns + 1))
 
        return -1  # target is unreachable

JavaScript

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function(deadends, target) {
    const dead = new Set(deadends);   // O(1) deadend lookup
 
    // Can't start if the initial state is a deadend
    if (dead.has('0000')) return -1;
 
    // Already at the target (problem says target !== '0000', but good to guard)
    if (target === '0000') return 0;
 
    const visited = new Set(['0000']); // prevent revisiting states
    const q = [['0000', 0]];          // queue: [state, turns]
    let head = 0;                      // array pointer for O(1) dequeue
 
    while (head < q.length) {
        const [state, turns] = q[head++];  // dequeue
 
        // Try rotating each of the 4 wheels in both directions
        for (let i = 0; i < 4; i++) {
            for (const delta of [1, -1]) {
                // Compute new digit with circular wrap
                const newDigit = (parseInt(state[i]) + delta + 10) % 10;
                // Construct new state string
                const newState = state.slice(0, i) + newDigit + state.slice(i + 1);
 
                // Reached the target
                if (newState === target) return turns + 1;
 
                // Only explore states that are not visited and not deadends
                if (!visited.has(newState) && !dead.has(newState)) {
                    visited.add(newState);
                    q.push([newState, turns + 1]);
                }
            }
        }
    }
 
    return -1;  // could not reach the target
};

Complexity Analysis

Approach	Time Complexity	Space Complexity
BFS on state space	O(10^4 * 4 * 2) = O(10^4)	O(10^4)

Time: There are at most 10,000 unique states ("0000" to "9999"). Each state has exactly 8 neighbors. Each state is processed at most once.
Space: The visited set and BFS queue each hold at most 10,000 entries. The deadends set holds at most 500 entries.

Follow-up Questions

Bidirectional BFS: Instead of searching from "0000" only, search simultaneously from "0000" and target, meeting in the middle. This reduces the explored states from O(10^4) to O(2 * 10^2), a dramatic speedup on large state spaces.
More than 4 wheels: If the lock had k wheels each with d digits, there are d^k states and 2k neighbors per state. BFS still works but may become infeasible for large k.
Return the actual sequence of states: Track a parent map parent[state] = prev_state. After reaching target, reconstruct the path by following parents back to "0000".
A heuristic:* Could use Manhattan distance between current state and target as a heuristic, potentially speeding up search in practice.

This Pattern Solves

LC 909 — Snakes and Ladders — BFS on game board states
LC 773 — Sliding Puzzle — BFS on board configuration strings
LC 127 — Word Ladder — BFS on word state space with one-character changes
LC 1926 — Nearest Exit from Entrance in Maze — BFS on grid states with exit condition

Key Takeaways

Open the Lock is a state-space BFS problem: state = 4-digit combination string, edges = 8 valid wheel turns
Initialize the visited set with all deadends before BFS — this prevents ever entering a deadend state
Each wheel turn uses modular arithmetic: (d + 1) % 10 for clockwise, (d - 1 + 10) % 10 for counterclockwise
BFS guarantees minimum turns because each BFS level represents exactly one turn
Check if the target itself is a deadend before starting — return -1 immediately if so
Time O(10^4 * 4 * 2) = O(80000), space O(10^4) — bounded by the number of possible 4-digit combinations
The state-space BFS template generalizes to any combinatorial puzzle: Rubik's cube, word ladder, 8-puzzle, sliding tiles

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Common Mistakes#

Solutions#

Python#

JavaScript#

Complexity Analysis#

Follow-up Questions#

This Pattern Solves#

Key Takeaways#

Related reading