DSA problem
Open the Lock
You have a lock with 4 wheels in front of you. Each wheel shows one digit from 0 to 9. Wheels rotate freely and wrap around: '0' can turn to '9' and '9' can turn to '0'. Each move rotates exactly one wheel by one slot. The lock starts at '0000', a 4-digit string.
You are given a list deadends of states the lock cannot be in (if any wheel ever shows that combination, the lock seizes), and a target state. Return the minimum total number of turns required to open the lock from '0000' to target, or -1 if the lock can never be opened.
Model each 4-digit state as a node in an unweighted graph. From any state, the 8 neighbours are obtained by rotating one of the 4 wheels forward or backward by one slot. Because every edge has the same cost, the shortest path is exactly the BFS distance from '0000' to target.
The optimal approach runs BFS from '0000', treating each deadend as a wall (never enqueue a deadend and don't expand from one). A visited set prevents revisiting states. With 10000 possible states and 8 neighbours each, BFS runs in O(10000 * 8) = O(N) time where N = 10^4. A bidirectional BFS from both '0000' and target can roughly halve the explored frontier in practice but isn't required.
Examples
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6deadends = ["8888"], target = "0009"1deadends = ["0000"], target = "8888"-1Constraints
- 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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.