Open the Lock
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 a shortest-path problem. Each 4-digit combination is a node in a graph. Two nodes are connected by an edge if they differ at exactly one position by exactly one slot (one wheel turn). The deadends are nodes we must avoid entirely. We need the shortest path from "0000" to the target, which is what BFS computes on an unweighted graph.
The state space is finite. There are only 10^4 = 10,000 possible combinations, and each combination has exactly 8 neighbors (4 wheels, each turned up or down). The graph is small enough that BFS over all of it is cheap.
Key Constraints:
deadends.length <= 500: at most 500 blocked states out of 10,000 total, so most of the graph stays reachable.target.length == 4and each character is a digit: the state space is fixed at 10,000 states regardless of input size, which bounds the work.- Each wheel wraps around (9 to 0 and 0 to 9): every state has exactly 8 neighbors, with no boundary case to special-case.
Approach 1: BFS
Intuition
The problem asks for the minimum number of moves where every move costs the same, which is a shortest-path query on an unweighted graph. BFS solves exactly that.
Treat each 4-digit combination ("0000" through "9999") as a node. Two nodes share an edge when one wheel turn separates them. From any combination, turning any of the 4 wheels up or down gives 8 neighbors. The deadends are nodes we remove from the graph: they cannot be visited.
BFS explores nodes level by level. Level 0 is "0000". Level 1 is every state reachable in one turn. Level 2 is every state reachable in two turns, and so on. The first time BFS reaches the target, the current level is the minimum number of turns. No shorter path exists, because BFS finishes every path of length k before touching any path of length k+1.
One edge case needs handling before the loop: if "0000" is itself a deadend, the lock is stuck at the start, so return -1.
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 expands outward from the source in every direction, including directions that lead away from the target. The next approach searches from both ends at once, so the two frontiers meet in the middle after far less expansion.
Approach 2: Bidirectional BFS
Intuition
Standard BFS expands from one end, and the number of states at each level grows quickly. If the shortest path has length d, BFS can touch up to O(8^d) states before reaching the target (the 10,000-state cap limits this in practice).
Bidirectional BFS expands from both ends at once. Instead of one frontier growing from "0000" to the target, it keeps two frontiers: one from the source and one from the target. Each step expands the smaller frontier. When the two frontiers overlap, the combined path is the shortest one.
For a shortest path of length 6, standard BFS explores states up to distance 6 from the start. Bidirectional BFS only reaches distance 3 from each end. Because the frontier grows by up to 8x per level, two depth-3 searches expand far fewer states than one depth-6 search.
Both searches still proceed level by level, so each frontier holds exactly the states at a fixed distance from its origin. When a state first appears in both frontiers, the forward side reached it in k turns and the backward side reached it in d - k turns, and the total k + (d - k) = d is the shortest path length. The edges are undirected (turning a wheel up is reversible by turning it down), so a path found backward from the target is a valid forward path to it.
Expanding the smaller frontier each step bounds the work: if one side has 10 states and the other has 1,000, expanding the smaller side adds at most 80 candidates instead of 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
Trace with no deadends and target "0003". The answer is 3 turns. Each step expands the smaller frontier, so the side being expanded alternates.
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.