You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
The lock initially starts at '0000', a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanation: A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid, because the wheels of the lock become stuck after the display becomes the dead end "0102".
Example 2:
Input: deadends = ["8888"], target = "0009" Output: 1 Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".
Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Explanation: We cannot reach the target without getting stuck.
Constraints:
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4deadends.target and deadends[i] consist of digits only.Problem Overview: You start with a 4‑wheel lock showing "0000". Each move rotates one wheel up or down by one digit. Some combinations are deadends and cannot be visited. The goal is to reach a target combination using the minimum number of moves.
The lock state space is small: each wheel has 10 digits, so there are at most 10^4 possible combinations. Each state can generate up to 8 neighbors (increment or decrement each of the four wheels). The problem becomes a shortest‑path search on an implicit graph where nodes are lock combinations and edges represent valid rotations.
Approach 1: Breadth‑First Search (BFS) (Time: O(10^4), Space: O(10^4))
Model the lock as a graph and run Breadth-First Search starting from "0000". BFS explores all combinations reachable in 1 move, then 2 moves, and so on, guaranteeing the first time you reach the target is the shortest path. Store deadends in a hash table for O(1) checks and maintain a visited set to avoid revisiting combinations.
For each state, generate its 8 neighbors by rotating each wheel forward or backward. For example, rotating the first wheel of "1234" produces "0234" and "2234". Push valid neighbors into the queue and track the number of levels processed. BFS works well here because the graph is small and unweighted, making level‑order traversal an exact match for the minimum move requirement.
Approach 2: Bidirectional Breadth‑First Search (Time: O(10^4), Space: O(10^4))
Bidirectional BFS improves search efficiency by expanding from both the start ("0000") and the target simultaneously. Instead of exploring the entire frontier from one side, maintain two frontiers and always expand the smaller one. When the frontiers intersect, the shortest path is found.
This approach drastically reduces the number of explored states because each search covers roughly half the distance. In a graph with branching factor b and depth d, regular BFS explores about b^d nodes, while bidirectional BFS explores roughly b^(d/2) from each side. Deadends and visited states are still tracked using a set, and neighbor generation follows the same wheel rotation logic as the standard BFS approach.
Recommended for interviews: Start with the standard BFS solution. It directly models the problem as a shortest‑path search on an unweighted graph and clearly demonstrates your understanding of graph traversal and state exploration. Once that solution is clear, mentioning bidirectional BFS shows deeper optimization awareness and familiarity with advanced search techniques used in graph problems involving symmetric start and target states.
The problem can be visualized as a graph traversal task, where each state of the lock is a node, and valid moves between states are edges. We use Breadth-First Search (BFS) to explore all possibilities level by level, which ensures that the first time we reach the target state, we have used the minimum number of steps possible.
To implement this approach, initialize a queue for BFS starting with the initial state '0000' and count as 0. Use a set to store deadends and another set for visited states to prevent reprocessing. For each current state, if it is the target, return the count. Otherwise, generate all possible next states by turning each wheel forward and backward, and enqueue all of them that aren't in deadends or the visited set.
The code implements a BFS approach using a queue where each element is a tuple containing the current state and the number of moves taken to reach it. The deadends and visited states are stored in sets to allow quick lookup operations. We iterate through each wheel of the lock, creating new states by incrementing or decrementing the current digit, making sure to wrap around from 9 to 0 or 0 to 9. If a state hasn't been visited or isn't a deadend, it's added to the queue of states to explore next.
Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states.
To further optimize the BFS approach, a Bidirectional BFS can be employed. We initiate two BFS processes, one from the initial state '0000' and the other from the target state. If they meet at any node, the combined path length gives the answer. This approach can significantly reduce the number of states explored as two searches from opposite ends tend to cover less ground.
The bidirectional BFS starts two searches: one from the initial state '0000' and the other from the target. During each iteration, we always expand the smaller frontier. If they meet, the shortest path is found. By swapping between the starting and ending search direction, we prevent excessive growth of either search frontier. Overall, this reduces the breadth of the search space.
C++
JavaScript
Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states. |
| Bidirectional Breadth-First Search | Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(10^4) | O(10^4) | General solution for shortest path in an unweighted state graph |
| Bidirectional BFS | O(10^4) worst case (often much faster) | O(10^4) | When both start and target states are known and search depth can be reduced |
Open the Lock - Leetcode 752 - Python • NeetCode • 54,650 views views
Watch 9 more video solutions →Practice Open the Lock with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor