Open the Lock
Last Updated: March 28, 2026
Understanding the Problem
We are navigating a 4-digit combination lock from "0000" to some target combination. Each move turns exactly one wheel by one position (up or down), and certain combinations are "deadends" that we cannot pass through. We need the shortest sequence of moves, or -1 if it is impossible.
This is really a shortest-path problem in disguise. Think of every possible 4-digit combination as a node in a graph. Two nodes are connected by an edge if they differ by exactly one digit by exactly one position (one wheel turn). The deadends are nodes we must avoid entirely. We need the shortest path from "0000" to the target, which is exactly what BFS does.
The key insight is recognizing the state space. There are only 10^4 = 10,000 possible combinations, and each combination has exactly 8 neighbors (4 wheels, each can go up or down). This is a small, manageable graph, and BFS will find the answer efficiently.
Key Constraints:
deadends.length <= 500-- At most 500 blocked states out of 10,000 total. Most of the graph remains navigable.target.length == 4and each character is a digit -- The state space is fixed at 10^4 = 10,000 states regardless of input size.- Each wheel wraps around (9 -> 0 and 0 -> 9) -- Every state has exactly 8 neighbors, no special boundary handling needed.
Approach 1: BFS
Intuition
Whenever you see "minimum number of moves" or "shortest path" in a problem where each move has equal cost, BFS should be your first thought. And that is exactly what this problem is asking.
Picture every possible 4-digit combination ("0000" through "9999") as a node in an enormous graph. Two nodes share an edge if you can get from one to the other with a single wheel turn. From any combination, you can turn any of the 4 wheels up or down by one, giving you exactly 8 neighbors. The deadends are simply nodes we delete from the graph, they cannot be visited.
BFS explores nodes level by level. Level 0 is "0000". Level 1 is all states reachable in one turn. Level 2 is all states reachable in two turns, and so on. The first time BFS reaches the target, we know that is the minimum number of turns. No shorter path exists because BFS explores every possibility of length k before anything of length k+1.
There is one edge case to handle upfront: if "0000" itself is a deadend, we cannot even start, so return -1 immediately.
Algorithm
- Add all deadends to a HashSet called
dead. - If "0000" is in
dead, return -1 immediately. - Create a queue and enqueue "0000". Create a visited set and add "0000".
- Initialize
turns = 0. - While the queue is not empty, process all nodes at the current level. For each node, if it equals the target, return
turns. Generate all 8 neighbors (4 wheels x 2 directions). For each neighbor not indeadand not invisited, add it tovisitedand enqueue it. After processing the entire level, incrementturns. - If BFS finishes without finding the target, return -1.
Example Walkthrough
Code
- Time Complexity: O(10^4 * 4). There are at most 10,000 possible states. BFS visits each state at most once, generating 8 neighbors per state with O(1) HashSet lookups.
- Space Complexity: O(10^4). The visited set and queue can hold at most 10,000 entries. The deadend set holds at most 500 entries.
Standard BFS explores outward from the source in all directions, even directions that move away from the target. What if we searched from both ends simultaneously, so the two frontiers meet in the middle much sooner?
Approach 2: Bidirectional BFS
Intuition
Standard BFS explores outward from one end, and the number of states at each level grows rapidly. If the shortest path has length d, BFS might explore O(8^d) states before reaching the target (though the 10,000-state cap limits this in practice).
Bidirectional BFS starts from both ends simultaneously. Instead of one frontier growing from "0000" to the target, we maintain two frontiers: one expanding from the source and one from the target. At each step, we expand the smaller frontier. When the two frontiers overlap, we have found the shortest path.
Imagine the shortest path has length 6. Standard BFS explores all states up to distance 6 from the start. Bidirectional BFS only needs to explore states up to distance 3 from each end. Since the number of states grows exponentially with distance (up to 8 neighbors each level), searching to depth 3 from both sides is much cheaper than searching to depth 6 from one side.
Bidirectional BFS is correct because it still explores states level by level from both ends. If the shortest path has length d, then at some level the forward frontier (at distance k from the start) and the backward frontier (at distance d - k from the target) will share a common state. The sum k + (d - k) = d gives us the correct shortest path length.
Expanding the smaller frontier at each step is a heuristic that minimizes the total number of states explored. If one frontier has 10 states and the other has 1,000, expanding the smaller one adds at most 80 new states, while expanding the larger one could add up to 8,000.
Algorithm
- Add all deadends to a HashSet called
dead. If "0000" is indead, return -1. - Create two sets:
frontSet = {"0000"}andbackSet = {target}. Create avisitedset containing both. - While both sets are non-empty, always expand the smaller set. For each node, generate all 8 neighbors. If a neighbor exists in the other set, return
turns + 1. Otherwise, if valid, add to the next frontier. - If the loop ends without the frontiers meeting, return -1.
Example Walkthrough
Code
- Time Complexity: O(10^4 * 4). Same worst-case as standard BFS since we might visit all 10,000 states. But in practice, bidirectional BFS explores far fewer states because the two frontiers meet in the middle.
- Space Complexity: O(10^4). We store the same visited set plus two frontier sets. In the worst case, the combined storage is still bounded by 10,000.