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.The key idea in #752 Open the Lock is to treat each lock combination as a node in a graph and find the shortest sequence of moves to reach the target. Each wheel rotation (up or down) creates a new neighboring state, giving up to 8 possible transitions from any combination.
A common and efficient strategy is Breadth-First Search (BFS). Start from the initial state "0000" and explore all reachable combinations level by level. Maintain a hash set for deadends and another set to track visited states so you never revisit the same combination. At each step, generate the next valid states by rotating each digit forward or backward.
BFS works well because it naturally finds the minimum number of moves required to reach the target. If the target is encountered during traversal, return the number of steps taken. If all states are exhausted without reaching it, the lock cannot be opened. The search space is bounded since there are only 10^4 possible combinations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search with visited set | O(10^4) | O(10^4) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We can think of this problem as a shortest path problem on a graph: there are `10000` nodes (strings `'0000'` to `'9999'`), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so `'0'` and `'9'` differ by 1), and if *both* nodes are not in `deadends`.
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.
Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states.
1import java.util.*;
2
3class Solution {
4 public int openLock(String[] deadends, String target) {
5 Set<String> deadset = new HashSet<>(Arrays.asList(deadends));
6 Queue<String> queue = new LinkedList<>();
7 Set<String> visited = new HashSet<>();
8 queue.offer("0000");
9 visited.add("0000");
10 int turns = 0;
11
12 while (!queue.isEmpty()) {
13 int size = queue.size();
14 for (int i = 0; i < size; i++) {
15 String position = queue.poll();
16 if (position.equals(target)) return turns;
17 if (deadset.contains(position)) continue;
18 for (int j = 0; j < 4; j++) {
19 char[] chars = position.toCharArray();
20 char orig = chars[j];
21 chars[j] = (char)((orig - '0' + 1) % 10 + '0');
22 String next = new String(chars);
23 if (!visited.contains(next)) {
24 queue.offer(next);
25 visited.add(next);
26 }
27 chars[j] = orig;
28 chars[j] = (char)((orig - '0' + 9) % 10 + '0');
29 next = new String(chars);
30 if (!visited.contains(next)) {
31 queue.offer(next);
32 visited.add(next);
33 }
34 }
35 }
36 turns++;
37 }
38 return -1;
39 }
40}The Java solution closely follows the BFS from the Python code. A queue stores states to explore, and we maintain a visited set to track states we've already processed. For each state, explore its neighbors by rotating each wheel one step forward and backward, checking to skip deadends and revisited states. The depth of the BFS tree is returned when the target state is reached.
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.
Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets.
1function openLock(deadends, target) {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Open the Lock is a popular interview-style problem because it tests graph traversal, BFS, and state-space exploration. Variations of this problem appear in coding interviews at major tech companies.
BFS explores states level by level, ensuring the first time the target combination is reached is with the minimum number of moves. This makes it ideal for shortest-path problems in unweighted graphs like this lock state space.
The optimal approach is Breadth-First Search (BFS). Since each lock combination can be viewed as a node and each wheel rotation forms an edge, BFS efficiently finds the shortest path from "0000" to the target while avoiding deadend states.
A queue is used to perform BFS traversal, while hash sets are used to store visited states and deadends. These structures allow constant-time checks to prevent revisiting combinations and to skip invalid states.
The approach is similar to the C++ solution but involves managing two sets, beginSet and endSet, that store states being explored from both directions. The search alternates between these two directions and explores neighbors by rotating each digit of the lock either forward or backward. This minimizes the states processed, especially when the target is near the searched edges.