Open the Lock
MedPrompt
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 == 4- target will not be in the list
deadends. targetanddeadends[i]consist of digits only.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as finding the shortest path in an unweighted graph. The lock combinations are the nodes, and a single turn of a wheel represents an edge. Breadth-First Search (BFS) is a perfect algorithm for this because it explores the graph level by level, guaranteeing that the first time we reach the target, it will be via the shortest possible path.
Algorithm
- Initialize a
Queuefor BFS and add the starting combination "0000". - Initialize a
Setcalledvisitedto store visited combinations and add alldeadendsto it. - If "0000" is in the
deadendsset, return -1 immediately. - Add "0000" to the
visitedset. - Initialize
turns = 0. - While the queue is not empty:
- Get the number of nodes at the current level,
level_size. - For
ifrom 0 tolevel_size - 1:- Dequeue the current combination
curr. - If
currequals thetarget, returnturns. - Generate all 8 possible next combinations by turning each of the 4 wheels one step forward and one step backward.
- For each
neighborcombination:- If
neighborhas not been visited and is not a deadend, add it to the queue and thevisitedset.
- If
- Dequeue the current combination
- Increment
turns.
- Get the number of nodes at the current level,
- If the loop finishes without finding the target, return -1.
Walkthrough
We start at the initial combination "0000". We use a queue to perform a level-order traversal of the state space graph. A visited set is crucial to keep track of combinations we've already processed, preventing cycles and redundant work. The deadends are pre-loaded into this visited set to treat them as inaccessible states. The search proceeds level by level. At each level, we explore all reachable combinations from the combinations of the previous level. The level number corresponds to the number of turns. If we encounter the target combination, we return the current level count. If the queue becomes empty before finding the target, it means the target is unreachable from the start.
class Solution { public int openLock(String[] deadends, String target) { Set<String> deadSet = new HashSet<>(Arrays.asList(deadends)); Set<String> visited = new HashSet<>(); Queue<String> queue = new LinkedList<>(); String start = "0000"; if (deadSet.contains(start)) { return -1; } queue.offer(start); visited.add(start); int turns = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { String currentLock = queue.poll(); if (currentLock.equals(target)) { return turns; } for (int j = 0; j < 4; j++) { char[] currentChars = currentLock.toCharArray(); char originalChar = currentChars[j]; // Turn forward currentChars[j] = (char) (((originalChar - '0' + 1) % 10) + '0'); String nextLock = new String(currentChars); if (!visited.contains(nextLock) && !deadSet.contains(nextLock)) { queue.offer(nextLock); visited.add(nextLock); } // Turn backward currentChars[j] = (char) (((originalChar - '0' + 9) % 10) + '0'); String prevLock = new String(currentChars); if (!visited.contains(prevLock) && !deadSet.contains(prevLock)) { queue.offer(prevLock); visited.add(prevLock); } currentChars[j] = originalChar; // backtrack for next wheel } } turns++; } return -1; // Target not reachable }}Complexity
Time
O(D + C * W), where D is the number of deadends, C is the total number of combinations (10^4), and W is the number of wheels (4). We visit each of the C states at most once. For each state, we generate 2*W neighbors. The initial processing of deadends takes O(D).
Space
O(D + C), where D is the number of deadends and C is the total number of combinations (10^4). The `queue` and `visited` set can store up to C combinations in the worst case. The `deadSet` stores D combinations.
Trade-offs
Pros
Guaranteed to find the shortest path.
Relatively straightforward to implement.
Handles all cases correctly.
Cons
Can be slow if the shortest path is long, as the search frontier (the queue size) can grow exponentially with the number of turns.
Explores a potentially large number of states before reaching the target.
Solutions
Solution
class Solution {private String start;private String target;private Set<String> s = new HashSet<>();public int openLock(String[] deadends, String target) { if ("0000".equals(target)) { return 0; } start = "0000"; this.target = target; for (String d : deadends) { s.add(d); } if (s.contains(start)) { return -1; } return bfs(); }private int bfs() { Map<String, Integer> m1 = new HashMap<>(); Map<String, Integer> m2 = new HashMap<>(); Deque<String> q1 = new ArrayDeque<>(); Deque<String> q2 = new ArrayDeque<>(); m1.put(start, 0); m2.put(target, 0); q1.offer(start); q2.offer(target); while (!q1.isEmpty() && !q2.isEmpty()) { int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2); if (t != -1) { return t; } } return -1; }private int extend(Map<String, Integer> m1, Map<String, Integer> m2, Deque<String> q) { for (int n = q.size(); n > 0; --n) { String p = q.poll(); int step = m1.get(p); for (String t : next(p)) { if (m1.containsKey(t) || s.contains(t)) { continue; } if (m2.containsKey(t)) { return step + 1 + m2.get(t); } m1.put(t, step + 1); q.offer(t); } } return -1; }private List<String> next(String t) { List res = new ArrayList<>(); char[] chars = t.toCharArray(); for (int i = 0; i < 4; ++i) { char c = chars[i]; chars[i] = c == '0' ? '9' : (char)(c - 1); res.add(String.valueOf(chars)); chars[i] = c == '9' ? '0' : (char)(c + 1); res.add(String.valueOf(chars)); chars[i] = c; } return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.