Open the Lock
Problem Statement
You have a lock with 4 wheels. Each wheel shows a digit from 0 to 9. One turn moves one wheel by one slot. A wheel wraps around: turning 9 up gives 0, and turning 0 down gives 9.
The lock starts at 0000. Some codes are dead ends. If the wheels show a dead end, the lock jams and you cannot go on from there. The target code opens the lock.
Return the fewest turns needed to get from 0000 to the target without ever showing a dead end. If the target cannot be reached, return -1. (If 0000 itself is a dead end, the answer is -1.)
deadends, a list of 4-digit codes that jam the lock. target, the 4-digit code that opens it.
The fewest number of turns, or -1 if the target cannot be reached.
The route 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202 has 6 turns and avoids every dead end. No shorter route exists.
Turning the last wheel down from 0 gives 9 in one turn.
All 8 codes one turn away from 8888 are dead ends, so the target is walled off.
- • There are between 1 and 500 dead ends.
- • Every code has exactly 4 digits, and uses only the digits 0 to 9.
- • The target is never one of the dead ends.
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Try every sequence of turns with a limit of 0, 1, 2, … until one reaches the target
BFS from 0000; each code is pushed once, and the dead ends are never entered
Choose a limit. Try every sequence of at most that many turns from 0000, never stepping onto a dead end. If one sequence reaches the target, the limit is the answer. If none does, raise the limit by 1 and search again.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.