Open the Lock LeetCode 752 Deep Dive

LeetCode 752 — Open the Lock presents you with a 4-wheel combination lock, each wheel displaying digits 0 through 9. The lock starts at "0000". Each move turns one wheel up or down by exactly one digit, with wrapping: turning 9 up gives 0, and turning 0 down gives 9.

You are given a list of deadend combinations — states that will lock the lock permanently if reached. You are also given a target combination. Your goal is to return the minimum number of moves required to reach the target from "0000", or -1 if it is impossible.

Key constraints to keep in mind:

The key insight is to model the lock as a graph. Each 4-digit combination is a node — there are exactly 10^4 = 10,000 possible states from "0000" to "9999". Each node has exactly 8 neighbors: for each of the 4 wheel positions, you can turn up or turn down, yielding 4 × 2 = 8 transitions.

Deadend combinations are simply blocked nodes — you cannot enter them. The problem reduces to: find the shortest path in an unweighted graph from "0000" to the target, avoiding blocked nodes. BFS is the canonical algorithm for shortest path in an unweighted graph.

Because all edges have equal weight (each turn costs 1 move), BFS explores states in order of increasing distance from the start. The first time BFS reaches the target, the current depth is guaranteed to be the minimum number of moves.

The BFS starts by enqueuing the initial state "0000" at depth 0. Before the main loop begins, pre-load all deadend combinations into the visited set — this elegantly blocks them from ever being enqueued. Also check immediately if "0000" is a deadend; if so, return -1.

For each state dequeued, generate all 8 neighbors by turning each of the 4 wheels up and down. For each neighbor, if it has not been visited, add it to the visited set and enqueue it with depth + 1. If the neighbor equals the target, return the current depth + 1.

If the BFS queue empties without finding the target, the target is unreachable and you return -1. The visited set ensures each of the 10,000 states is processed at most once, giving O(10,000 × 4) = O(40,000) total operations.

For a given 4-digit state, generating the 8 neighbors is the core inner loop. Iterate over each of the 4 positions. For position i, extract the current digit as an integer. Turning up means (digit + 1) % 10 — this handles the 9 → 0 wrap. Turning down means (digit - 1 + 10) % 10 — the + 10 before modulo handles the 0 → 9 wrap without negative values.

Construct the new state string by replacing character at position i with the new digit, keeping all other characters the same. Yield or collect the resulting 4-digit string. Repeat for both directions at all 4 positions to produce all 8 neighbors.

In Python this is typically done with a list conversion of the string for easy character replacement. In Java, a StringBuilder or char array works well. The logic is identical: for each index i, produce two new strings — one with digit[i] incremented mod 10, one with digit[i] decremented mod 10.

Standard BFS from "0000" explores states in expanding rings of radius 1, 2, 3... up to the answer depth d. The total states explored is roughly O(8^d) in the worst case, though bounded by 10,000. Bidirectional BFS cuts this dramatically.

In bidirectional BFS, you maintain two frontiers: one expanding from "0000" and one expanding from the target. At each step, expand the smaller frontier. When the two frontiers overlap — a state appears in both — the total depth of that state from both ends is the answer.

For Open the Lock this reduces the effective search radius from d to roughly d/2 on each side, changing exploration from O(10^4) states in one direction to O(2 × 10^2) states total in balanced cases. While the asymptotic bound on this problem is still 10,000 states (the graph is small), bidirectional BFS is a key technique in larger state-space problems where the speedup is essential.

In Python, use collections.deque for O(1) popleft. Initialize: dead = set(deadends), visited = set(dead), queue = deque([("0000", 0)]). If "0000" in dead, return -1. In the BFS loop: state, steps = queue.popleft(). If state == target, return steps. For each of 4 positions and 2 directions, compute neighbor; if not in visited, add to visited and enqueue with steps + 1.

In Java, use a Queue<String> with LinkedList, and a Set<String> for visited initialized with Arrays.asList(deadends). Time complexity: O(10^4 × 4) = O(40,000) for neighbor generation across all states. Space complexity: O(10^4) for the visited set and queue.

Critical edge case: if the target equals "0000", return 0 immediately — no moves needed. If "0000" is in deadends, return -1 before enqueueing. These two checks prevent subtle bugs in otherwise correct BFS implementations.

Open the Lock belongs to the BFS state-space family — problems where each "node" is an abstract state and edges are valid transitions. Word Ladder (LeetCode 127) is the closest relative: each word is a node, and edges connect words differing by one letter. The deadend avoidance in Open the Lock mirrors the restricted word list in Word Ladder.

Shortest Path in Binary Matrix (LeetCode 1091) and Minimum Genetic Mutation (LeetCode 433) follow the same pattern. In each case: model states as nodes, define valid transitions as edges, run BFS from start to end, return depth or -1. The only variation is how you define the state space and how you generate neighbors.

Recognizing this family is a powerful interview skill. Once you see "minimum steps from A to B with constraints on intermediate states," reach for BFS on a state-space graph. Open the Lock is the canonical training problem for this pattern — master it and the entire family becomes approachable.