The Open the Lock problem presents a combination lock with 4 wheels (0000 to 9999). Each turn moves one wheel up or down by 1 (wrapping around). Given a target combination and a set of deadends (forbidden combinations), find the minimum turns to reach the target from 0000. This coding problem is a classic BFS shortest-path problem on a state graph.
J.P. Morgan, Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests BFS on an implicit graph of states. The state space (10^4 = 10000 combinations) is small enough for BFS, and deadend avoidance is the constraint. The array, BFS, hash table, and string interview pattern is the core.
BFS on state graph. Start at "0000". For each state, generate up to 8 neighbors (each of 4 wheels can go up or down). Skip states in deadends or already visited. BFS guarantees minimum turns (unweighted shortest path). Return level when target is reached, -1 if not reachable.
target="0202", deadends=["0201","0101","0102","1212","2002"]. BFS from "0000". Level 1: ["1000","0100","0010","0001","9000","0900","0090","0009"]. Level 2: continue expanding. Minimum turns = 6 (some path avoids deadends to reach "0202").
Open the Lock exemplifies BFS on an implicit state graph. The state is the 4-digit combination. Generate neighbors by modifying one character at a time with wrap-around. This pattern applies to puzzle BFS problems: Rubik's cube states, word ladder, sliding tile puzzles. Always verify: (1) deadend check before processing, (2) "0000" deadend check, (3) modular arithmetic for wrap-around digits.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Word Subsets | Medium | Solve | |
| Minimum Genetic Mutation | Medium | Solve | |
| Vowel Spellchecker | Medium | Solve | |
| Find Duplicate File in System | Medium | Solve | |
| Group Shifted Strings | Medium | Solve |
