752. Open the Lock

The Open the Lock problem is a well-known interview question that helps build intuition around shortest-path problems. It looks simple at first, but quickly becomes tricky once you account for deadends and repeated states. Many candidates try to reason about moves locally, only to realize that a systematic approach is required. This problem is a great way to understand how breadth-first search can be used to explore all valid possibilities while guaranteeing the minimum number of moves.

Problem statement

You’re given a lock with four circular wheels, each labeled with digits from '0' to '9'. The lock starts at the combination "0000". In one move, you can rotate any single wheel one step forward or backward, with wrap-around behavior (for example, '9' → '0' and '0' → '9').

You’re also given a list of deadends. If the lock ever shows one of these combinations, it becomes stuck and can no longer be turned. Given a target combination, your task is to return the minimum number of moves required to open the lock, or -1 if it is impossible.

At first glance, this may seem like a simple transformation problem. However, because each move creates multiple new states and deadends block progress, the real challenge is finding the shortest path without revisiting states or getting stuck.

Constraints:

• 1 <= deadends.length <= 500
• deadends[i].length == 4
• target.length == 4
• target will not be in the list deadends.
• target and deadends[i] consist of digits only.

Examples

Why enumerating all possibilities doesn’t scale

A naive approach might try all possible sequences of wheel rotations until the target is reached. However, each lock state can generate up to 8 neighboring states (4 wheels x 2 directions), and the total number of possible combinations is 10⁴.

Without a systematic strategy, this leads to:

• Repeated exploration of the same states
• Exponential growth in possible paths
• Inefficient handling of deadends

To solve this efficiently, we need a method that explores states level by level, avoids revisiting states, and guarantees the shortest path.

Optimized approach using Breadth-First Search

This problem can be modeled as a graph traversal problem:

• Each lock combination is a node
• An edge exists between two nodes if one move transforms one combination into the other

Since every move has the same cost (one turn), breadth-first search (BFS) is the ideal approach. BFS explores all states reachable in k moves before moving on to k + 1 moves, ensuring that the first time we reach the target is with the minimum number of moves.

Why breadth-first search works well here

The state space is finite and reasonably small (at most 10,000 combinations). BFS efficiently explores this space while guaranteeing optimal results.

This makes the approach:

• Correct: Always finds the minimum number of moves
• Efficient: Avoids unnecessary revisits
• Predictable: Bounded time and space usage

Step-by-step algorithm

The following algorithmic steps describe how to open the lock efficiently:

1. Convert the deadends list into a set for fast lookup.
2. If the starting state "0000" is a deadend, return -1.
3. Initialize a queue with the starting state "0000" and move count 0.
4. Maintain a visited set to track explored combinations.
5. While the queue is not empty:
   1. Dequeue the current state and its move count.
   2. If the current state equals the target, return the move count.
   3. For each of the 4 wheel positions:
      1. Rotate the wheel one step forward and backward to generate new states.
      2. If a generated state is not a deadend and not visited:
         1. Add it to the queue with move count + 1.
         2. Mark it as visited.
6. If the target is never reached, return -1.

To better understand the algorithm, let’s walk through an illustration example below.

1 / 5

Python implementation

Let’s look at the code for the solution we just discussed.

from collections import deque

def openLock(deadends, target):
    # Convert deadends list to a set for O(1) lookup
    dead = set(deadends)

    # Starting state of the lock
    start = "0000"

    # If the starting state itself is a deadend, we cannot move
    if start in dead:
        return -1

    # Queue for BFS: stores (current_state, moves_taken)
    queue = deque([(start, 0)])

    # Set to track visited states to avoid revisiting
    visited = set([start])

    # Perform BFS
    while queue:
        state, moves = queue.popleft()

        # If we reached the target, return the number of moves
        if state == target:
            return moves

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

            # Rotate wheel forward (+1) and backward (-1)
            for diff in (-1, 1):
                new_digit = (digit + diff) % 10

                # Form the next lock state
                next_state = (
                    state[:i] + str(new_digit) + state[i + 1:]
                )

                # Add the state to the queue if it's valid
                if next_state not in dead and next_state not in visited:
                    visited.add(next_state)
                    queue.append((next_state, moves + 1))

    # If BFS completes without finding the target
    return -1

def main():
    test_cases = [
        (["0201","0101","0102","1212","2002"], "0202"),
        (["8888"], "0009"),
        (["8887","8889","8878","8898","8788","8988","7888","9888"], "8888"),
        ([], "0000"),
        (["0000"], "8888")
    ]

    for idx, (deadends, target) in enumerate(test_cases, start=1):
        result = openLock(deadends, target)

        print(f"{idx}.\tDeadends: {deadends}")
        print(f"   \tTarget: {target}")
        print(f"   \tMinimum moves: {result}")
        print("-" * 100)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of this solution is 10⁴. Each possible lock combination is visited at most once, and each visit generates a constant number of neighboring states.

Space complexity

The space complexity of this solution is 10⁴. The queue and visited set may store all possible combinations in the worst case.

Edge cases

• Starting state is a deadend
  • Example: deadends = ["0000"] → return -1.
• Target is the starting state
  • Example: target = "0000" → return 0.
• Target completely blocked by deadends
  • All paths to the target pass through deadends.

Common pitfalls

• Using DFS instead of BFS: Depth-first search does not guarantee the shortest path.
• Forgetting to track visited states: Leads to infinite loops or redundant work.
• Incorrect wrap-around logic: Digits must wrap correctly from '9' to '0' and '0' to '9'.