Open the Lock

Difficulty: Medium Source: NeetCode

Problem

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0' through '9'. The wheels can rotate freely and wrap around (i.e., '9' goes to '0' and vice versa).

The lock initially starts at "0000", representing all wheels at '0'.

You are given a list of deadends and a target string. Return the minimum total number of turns required to open the lock, or return -1 if it is impossible.

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

Example 2: Input: deadends = ["8888"], target = "0009" Output: 1

Example 3: Input: deadends = ["0000"], target = "8888" Output: -1

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• BFS for shortest path — minimum turns = minimum moves in a graph
• State-space search — each unique 4-digit string is a node in the graph
• Neighbor generation — at each state, there are 8 possible transitions (each of 4 wheels ±1)

1. Brute Force (BFS without optimization)

Intuition

Model this as a graph problem: each 4-digit string is a node, and two nodes are connected if they differ by exactly one digit’s rotation. We want the shortest path from "0000" to target. BFS gives shortest path in an unweighted graph. The only twist is avoiding deadends.

Algorithm

1. If "0000" is in deadends, return -1.
2. Use BFS starting from "0000" with distance 0.
3. At each state, generate 8 neighbors (4 wheels × 2 directions).
4. Skip visited states and deadends.
5. Return the distance when target is reached, or -1 if queue empties.

Solution

from collections import deque

def openLock(deadends: list[str], target: str) -> int:
    dead = set(deadends)
    if "0000" in dead:
        return -1
    if target == "0000":
        return 0

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

    while queue:
        state, turns = queue.popleft()
        if state == target:
            return turns

        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 not in visited and new_state not in dead:
                    visited.add(new_state)
                    queue.append((new_state, turns + 1))

    return -1


print(openLock(["0201","0101","0102","1212","2002"], "0202"))  # 6
print(openLock(["8888"], "0009"))                              # 1
print(openLock(["0000"], "8888"))                              # -1

Complexity

• Time: O(10^4 * 4 * 2) — at most 10,000 states, each generating 8 neighbors
• Space: O(10^4) for visited set and queue

2. Bidirectional BFS

Intuition

Standard BFS expands outward from the start. Bidirectional BFS expands simultaneously from both the start ("0000") and the goal (target). When the two frontiers meet, we’ve found the shortest path. In practice this can halve the search space — instead of exploring a ball of radius d, you explore two balls of radius d/2.

Algorithm

1. Maintain two frontiers: begin (from start) and end (from target).
2. At each step, expand the smaller frontier: generate all neighbors, skip visited/dead.
3. If a new neighbor appears in the other frontier, return the current turn count + 1.
4. Use two separate visited sets visited_begin and visited_end.

Solution

def openLock(deadends: list[str], target: str) -> int:
    dead = set(deadends)
    if "0000" in dead or target in dead:
        return -1
    if target == "0000":
        return 0

    def neighbors(state):
        result = []
        for i in range(4):
            d = int(state[i])
            for delta in [1, -1]:
                result.append(state[:i] + str((d + delta) % 10) + state[i+1:])
        return result

    begin = {"0000"}
    end = {target}
    visited = {"0000", target}
    turns = 0

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

        next_begin = set()
        for state in begin:
            for nb in neighbors(state):
                if nb in end:
                    return turns + 1
                if nb not in visited and nb not in dead:
                    visited.add(nb)
                    next_begin.add(nb)
        begin = next_begin
        turns += 1

    return -1


print(openLock(["0201","0101","0102","1212","2002"], "0202"))  # 6
print(openLock(["8888"], "0009"))                              # 1
print(openLock(["0000"], "8888"))                              # -1
print(openLock([], "0001"))                                    # 1

Complexity

• Time: O(10^4) but with smaller constant due to bidirectional expansion
• Space: O(10^4)

Common Pitfalls

Starting state in deadends. If "0000" is a deadend, we can’t even begin — return -1 immediately.

Neighbor generation with wrapping. Digit 9 + 1 = 0 and digit 0 - 1 = 9. Use (digit + delta) % 10 to handle wrapping correctly.

Marking visited before enqueuing. Add new states to visited when generating neighbors, not when dequeuing. This prevents the same state from being enqueued multiple times.