Open the Lock LeetCode Solution: BFS on a State-Space Graph

LeetCode 752 — Open the Lock — is one of the cleanest examples of BFS on an implicit graph you will find in interview prep. The problem asks you to turn a 4-wheel combination lock from "0000" to a given target, one digit at a time, while avoiding a set of deadend combinations. Each turn moves one wheel up or down by one position, wrapping from 9 to 0 and back.

What makes this problem special is that you never receive an adjacency list or an edge array. The graph exists only in the rules: every 4-digit combination is a node, and every single-digit turn creates an edge to one of 8 neighbors. Recognizing this implicit graph structure is the key insight, and once you see it, BFS gives you the shortest number of turns automatically.

This open the lock leetcode problem is a staple at companies like Google, Amazon, and Meta because it tests whether you can translate a real-world scenario into a graph search — exactly the skill that separates pattern-matchers from genuine problem-solvers.

You start at "0000" and need to reach a target combination like "0202". On each move you pick one of the four wheels and turn it one slot up or down. Turning the first wheel of "0000" up gives "1000"; turning it down gives "9000". Each state therefore has exactly 8 neighbors — two per wheel.

The twist is the deadends array: a list of combinations that must never be visited. If you land on a deadend the lock jams permanently. Your job is to find the minimum number of turns to reach the target while completely avoiding every deadend, or return -1 if no path exists.

The total state space is 10^4 = 10,000 combinations (0000 through 9999). That is small enough to explore exhaustively, which is why BFS — not Dijkstra or A* — is the right tool here. Every edge has weight 1, and BFS explores states layer by layer, guaranteeing the first time you reach the target is with the fewest moves.

BFS is the canonical shortest-path algorithm for unweighted graphs, and Open the Lock is unweighted because every turn costs exactly 1 move. When you enqueue all states reachable in k turns before exploring any state at k+1 turns, BFS guarantees the first arrival at the target is optimal.

The implicit graph here has up to 10,000 nodes and 80,000 directed edges (8 per node). BFS visits each node at most once thanks to the visited set, so the time complexity is O(10^4 * 4) — effectively O(40,000) — which is essentially constant. Space complexity is also O(10^4) for the queue and visited set.

This is the same BFS-on-implicit-graph pattern you will see in Word Ladder (LeetCode 127), where each word is a node and each single-letter change is an edge. If you master the pattern on Open the Lock, Word Ladder becomes straightforward — and vice versa.

The BFS solution follows a clean three-phase structure: initialize, generate neighbors, and explore level by level. Here is the step-by-step approach that interviewers expect to see.

First, add all deadends to a hash set for O(1) lookup. Then check two immediate edge cases: if "0000" is a deadend, return -1 right away; if the target is "0000", return 0. Initialize your queue with "0000" and add it to visited.

For each state you dequeue, generate all 8 neighbors. For each of the 4 wheel positions, compute the digit-up and digit-down values with wrapping (using modular arithmetic: (d+1)%10 and (d+9)%10). If a neighbor equals the target, return the current depth + 1. If the neighbor is not in visited and not a deadend, enqueue it and mark it visited.

The entire BFS loop processes at most 10,000 states. If the queue empties without reaching the target, return -1.

Standard BFS explores all 10,000 states in the worst case. Bidirectional BFS can cut the search space dramatically by running two BFS frontiers simultaneously — one from "0000" and one from the target — and stopping when they meet.

The idea is simple: maintain two sets (frontStart and frontEnd) instead of a single queue. On each iteration, expand the smaller frontier. When generating neighbors for a state in frontStart, check if the neighbor exists in frontEnd — if it does, the two searches have met and you can return the total depth.

Bidirectional BFS reduces the effective branching from O(b^d) to O(b^{d/2}) where b is the branching factor (8) and d is the solution depth. For shallow solutions this barely matters, but for deep ones it can be orders of magnitude faster. In practice, interviewers are impressed if you mention this optimization even if they do not require you to implement it.

One subtle detail: you must also check both frontiers against the deadend set. A deadend blocks traversal from either direction, so both frontStart and frontEnd must skip deadend states during neighbor generation.

The most common mistake in Open the Lock is forgetting to check whether "0000" itself is a deadend. If the starting state is blocked, no BFS can even begin — you must return -1 before touching the queue. This edge case appears in many test suites and is the single most frequent reason for wrong answers on this problem.

Another subtle case: the target could be "0000". If no deadend blocks the start, you need zero moves. Make sure your code handles this before entering the BFS loop, or you will process unnecessary states.

A third pitfall is treating deadends as visited only during initialization. Some candidates add deadends to the visited set upfront (which works and is actually a clean approach), while others check the deadend set during neighbor generation. Both are correct, but mixing the two or forgetting one path leads to bugs. Pick one strategy and apply it consistently.

Open the Lock is the gateway problem for implicit-graph BFS. Once you internalize the pattern — define your state, enumerate transitions, run BFS, track visited — you can apply it to a wide family of problems: Word Ladder (LeetCode 127), Sliding Puzzle (LeetCode 773), Minimum Genetic Mutation (LeetCode 433), and any problem where the "graph" is not given explicitly but emerges from the rules.

The key takeaway is that BFS does not require an adjacency list. Any problem where you can define a start state, a goal state, and a neighbor-generation function is a BFS problem in disguise. The state can be a string, a tuple, a bitmask, or even a serialized grid — the pattern is the same.

If you are preparing for coding interviews, drill this problem until the neighbor-generation loop is second nature. Then try Word Ladder, Sliding Puzzle, and Minimum Genetic Mutation to solidify the pattern. YeetCode flashcards can help you review these implicit-graph BFS problems with spaced repetition so the pattern sticks long-term — not just the night before your interview.