Open the Lock — BFS on State Space (LeetCode 752)

Open the Lock (LeetCode 752) is a brilliant example of BFS on an implicit graph. You have a 4-digit lock starting at "0000". Each move turns one wheel by one position (up or down, wrapping 9 to 0 and 0 to 9). Some combinations are deadends. Find the minimum number of moves to reach the target.

The Problem

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

Explanation: "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"
Each step turns exactly one wheel by one position.

Why BFS?

Each lock state is a node in an implicit graph. Each node has exactly 8 neighbors (4 wheels x 2 directions). We want the shortest path from "0000" to target. BFS on an unweighted graph always finds the shortest path.

The state space has 10^4 = 10,000 possible combinations — completely manageable.

BFS Solution

from collections import deque

def openLock(deadends, target):
    """
    BFS on 4-digit lock state space.
    Time: O(10^4 * 4) = O(40,000) — constant
    Space: O(10^4) for visited set
    """
    dead = set(deadends)

    # Edge case: start is a deadend
    if "0000" in dead:
        return -1
    if target == "0000":
        return 0

    visited = {"0000"}
    queue = deque([("0000", 0)])

    while queue:
        state, moves = queue.popleft()

        # Try turning each of the 4 wheels
        for i in range(4):
            digit = int(state[i])

            for delta in (1, -1):
                new_digit = (digit + delta) % 10
                new_state = state[:i] + str(new_digit) + state[i+1:]

                if new_state == target:
                    return moves + 1

                if new_state not in visited and new_state not in dead:
                    visited.add(new_state)
                    queue.append((new_state, moves + 1))

    return -1  # Target unreachable

Step-by-Step Trace

deadends = {"0201", "0101", "0102", "1212", "2002"}, target = "0202"

Move 0: queue = ["0000"]
  From "0000", generate 8 neighbors:
    "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"
  None are deadends → all enqueued

Move 1: process "1000", "9000", "0100", ...
  From "1000" → "2000", "0000"(visited), "1100", "1900", ...
  From "0100" → "1100"(dup), "0200", "0110", ...
  "0101" is a deadend → skip
  "0200" enqueued

Move 2: process "1100", "0200", ...
  From "1100" → "1200", "1200" enqueued
  From "0200" → "0201"(deadend), "0200" neighbors...

Move 3: From "1200" → "1201" enqueued

Move 4: From "1201" → "1202" enqueued

Move 5: From "1202" → "0202" = target!

Return 6

Generating Neighbors Helper

For cleaner code, you can extract neighbor generation:

def get_neighbors(state):
    """Generate all 8 neighbors of a lock state."""
    neighbors = []
    for i in range(4):
        digit = int(state[i])
        for delta in (1, -1):
            new_digit = (digit + delta) % 10
            new_state = state[:i] + str(new_digit) + state[i+1:]
            neighbors.append(new_state)
    return neighbors

Optimization: Bidirectional BFS

Standard BFS explores outward from "0000". Bidirectional BFS explores from both "0000" and target simultaneously, meeting in the middle. This reduces the search space dramatically.

def openLock_bidirectional(deadends, target):
    """
    Bidirectional BFS — expands from both ends.
    Significantly faster in practice for large state spaces.
    """
    dead = set(deadends)
    if "0000" in dead or target in dead:
        return -1
    if target == "0000":
        return 0

    front = {"0000"}
    back = {target}
    visited = {"0000", target}
    moves = 0

    while front and back:
        # Always expand the smaller frontier
        if len(front) > len(back):
            front, back = back, front

        next_front = set()
        for state in front:
            for i in range(4):
                digit = int(state[i])
                for delta in (1, -1):
                    new_digit = (digit + delta) % 10
                    new_state = state[:i] + str(new_digit) + state[i+1:]

                    if new_state in back:
                        return moves + 1

                    if new_state not in visited and new_state not in dead:
                        visited.add(new_state)
                        next_front.add(new_state)

        front = next_front
        moves += 1

    return -1

Complexity Analysis

Approach	Time	Space
Standard BFS	O(10^4 x 4) = O(40,000)	O(10^4)
Bidirectional BFS	O(2 x 10^2 x 4) best case	O(10^4)

Since the state space is bounded at 10,000 nodes, both approaches are effectively constant time. Bidirectional BFS shines more on larger state spaces.

Edge Cases

# Start is a deadend
assert openLock(["0000"], "8888") == -1

# Target is "0000" (already there)
assert openLock(["8888"], "0000") == 0

# Target is unreachable (all neighbors of "0000" are deadends)
assert openLock(["1000","9000","0100","0900",
                 "0010","0090","0001","0009"], "9999") == -1

# No deadends — shortest path exists
assert openLock([], "0009") == 1

When to Use This Pattern

Use BFS on implicit state space when:

• The problem has a start state and goal state
• Each state has a finite, enumerable set of transitions
• You need the minimum number of moves/operations
• The state space is bounded (not infinite in practice)

Classic examples: sliding puzzles, word transformations, Rubik’s cube, and any “minimum operations” problem with discrete states.

Common Mistakes

1. Forgetting to check if “0000” is a deadend — return -1 immediately
2. Not using a visited set — BFS without visited enters infinite loops
3. String mutation errors — in Python, strings are immutable; build new strings carefully
4. Forgetting wraparound — 0-1 = 9 and 9+1 = 0

Related Problems

Problem	Key Difference
Word Ladder (LC 127)	BFS on words instead of digits
Sliding Puzzle (LC 773)	2x3 board state space
Minimum Genetic Mutation (LC 433)	BFS on gene strings
Shortest Path in Binary Matrix (LC 1091)	BFS on grid

Key Takeaways

• Model the 4-digit lock as a graph with 10,000 nodes and 8 edges per node
• BFS guarantees the shortest path on this unweighted implicit graph
• Deadends are simply nodes removed from the graph
• Bidirectional BFS is a powerful optimization for state-space search
• Always handle the edge case where the start state is blocked