LeetCode 752: Open the Lock

Problem Restatement

We have a lock with four wheels.

Each wheel contains digits from 0 to 9.

The lock starts at:

"0000"

In one move, we can rotate exactly one wheel by one step.

The digits wrap around:

9 -> 0
0 -> 9

Some lock states are deadends. If the lock reaches one of those states, it gets stuck and cannot move anymore.

Given a list of deadends and a target, return the minimum number of moves needed to reach target from "0000".

If the target cannot be reached, return -1.

Input and Output

Example function shape:

def openLock(deadends: list[str], target: str) -> int:
    ...

Examples

Input:

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

Output:

6

One valid path is:

0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202

This takes 6 moves.

Another possible path may get stuck:

0000 -> 0001 -> 0002 -> 0102

The state "0102" is a deadend, so that path cannot continue.

Another example:

deadends = ["8888"]
target = "0009"

Output:

1

We can rotate the last wheel backward:

0000 -> 0009

First Thought: Try All Move Sequences

One direct idea is to try every possible sequence of wheel turns.

From each state, there are 8 possible moves:

For each of the 4 wheels:

1. turn it forward
2. turn it backward

For example, from "0000" we can move to:

1000
9000
0100
0900
0010
0090
0001
0009

The problem with raw recursion or depth-first search is that it may follow a long path before trying a shorter one.

But we need the minimum number of moves.

This is a shortest path problem.

Key Insight

Each lock state is a node in a graph.

Each valid one-wheel turn is an edge.

All edges have the same cost: 1.

So the problem asks for the shortest path from "0000" to target in an unweighted graph.

Breadth-first search is the natural algorithm for this.

BFS explores states by distance:

The first time BFS reaches target, that distance is the minimum number of moves.

Generating Neighbor States

From one lock state, we generate 8 neighbors.

Suppose the state is:

"1234"

For wheel index 0, digit 1 can become:

2
0

So we get:

2234
0234

For each digit d, the next digit forward is:

(d + 1) % 10

The next digit backward is:

(d - 1) % 10

The modulo handles wraparound:

9 + 1 -> 0
0 - 1 -> 9

Helper function:

def neighbors(state: str) -> list[str]:
    ans = []

    for i in range(4):
        digit = int(state[i])

        for move in (-1, 1):
            next_digit = (digit + move) % 10
            next_state = state[:i] + str(next_digit) + state[i + 1:]
            ans.append(next_state)

    return ans

Algorithm

1. Convert deadends into a set for fast lookup.
2. If "0000" is a deadend, return -1.
3. Start BFS from "0000".
4. Store visited states so we do not process the same state repeatedly.
5. For each BFS level:
   1. Pop all states at the current distance.
   2. If a state equals target, return the distance.
   3. Generate its neighbors.
   4. Add valid, unvisited, non-deadend neighbors to the queue.
6. If BFS finishes without reaching target, return -1.

Correctness

We model each lock state as a graph node and each legal wheel turn as an edge.

Every edge has cost 1, because every move turns exactly one wheel by one slot.

BFS processes nodes in increasing order of distance from the starting state "0000".

At distance 0, it processes only "0000".

At distance 1, it processes all states reachable in one move.

At distance 2, it processes all states reachable in two moves.

This continues level by level.

The algorithm never explores a deadend, so every state it uses is valid.

The visited set ensures each state is processed at most once. Once BFS reaches a state, it has already found the shortest path to that state, because BFS reaches states in increasing distance order.

Therefore, when the algorithm first sees target, the current distance is the minimum number of moves needed to open the lock.

If BFS ends without seeing target, then every reachable valid state has been explored. In that case, no valid path exists, so returning -1 is correct.

Complexity

There are only 10,000 possible lock states, from "0000" to "9999".

Each state has at most 8 neighbors.

Since 10000 is fixed for this problem, the running time is effectively constant with respect to normal input size.

Implementation

from collections import deque

class Solution:
    def openLock(self, deadends: list[str], target: str) -> int:
        dead = set(deadends)

        if "0000" in dead:
            return -1

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

        while queue:
            level_size = len(queue)

            for _ in range(level_size):
                state = queue.popleft()

                if state == target:
                    return moves

                for i in range(4):
                    digit = int(state[i])

                    for step in (-1, 1):
                        next_digit = (digit + step) % 10
                        next_state = state[:i] + str(next_digit) + state[i + 1:]

                        if next_state in dead:
                            continue

                        if next_state in visited:
                            continue

                        visited.add(next_state)
                        queue.append(next_state)

            moves += 1

        return -1

Code Explanation

We first store deadends in a set:

dead = set(deadends)

This lets us check whether a state is blocked in expected constant time.

If the starting state is blocked, there is no move we can make:

if "0000" in dead:
    return -1

Then we start BFS:

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

The queue stores states to process.

The visited set prevents cycles.

The variable moves stores the current BFS level.

For each level:

level_size = len(queue)

We process exactly the states that are reachable in moves turns.

When we pop a state:

state = queue.popleft()

we check whether it is the target:

if state == target:
    return moves

Then we generate all one-move neighbors by trying both directions on each wheel.

for i in range(4):
    digit = int(state[i])

    for step in (-1, 1):
        next_digit = (digit + step) % 10

The modulo makes the wheel circular.

So 9 + 1 becomes 0, and 0 - 1 becomes 9.

We build the next lock state with string slicing:

next_state = state[:i] + str(next_digit) + state[i + 1:]

Then we skip blocked or already visited states:

if next_state in dead:
    continue

if next_state in visited:
    continue

Valid new states are marked visited and added to the queue:

visited.add(next_state)
queue.append(next_state)

After finishing the whole level, we increase the move count:

moves += 1

If the queue becomes empty, then all reachable states were checked and the target was not found.

return -1

Testing

def run_tests():
    s = Solution()

    assert s.openLock(
        ["0201", "0101", "0102", "1212", "2002"],
        "0202",
    ) == 6

    assert s.openLock(
        ["8888"],
        "0009",
    ) == 1

    assert s.openLock(
        ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"],
        "8888",
    ) == -1

    assert s.openLock(
        ["0000"],
        "8888",
    ) == -1

    assert s.openLock(
        [],
        "0000",
    ) == 0

    print("all tests passed")

run_tests()

Test meaning: