Open the Lock
Description
You have a lock with 4 circular wheels. Each wheel has 10 slots labeled '0' through '9'. The wheels wrap around: turning '9' forward gives '0', and turning '0' backward gives '9'. Each move consists of turning one wheel by one slot (either forward or backward).
The lock starts at the combination "0000".
You are given a list of deadends — if the lock ever displays any of these codes, the wheels jam and you can no longer turn them.
Given a target combination, return the minimum total number of single-wheel turns needed to reach the target from "0000". If it is impossible to reach the target without hitting a deadend, return -1.
Examples
Example 1
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: One valid sequence of moves is:
"0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"
Each arrow represents turning one wheel by one slot. A path like "0000" → "0001" → "0002" → "0102" → "0202" is invalid because "0102" is a deadend — the wheels would jam before reaching the target. The shortest valid path requires 6 turns.
Example 2
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We turn the last wheel backward once: "0000" → "0009". The wheel wraps from '0' to '9'. The deadend "8888" is never encountered, so a single turn suffices.
Example 3
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: Every combination that is exactly one turn away from "8888" is a deadend. To reach "8888", we would have to pass through one of these blocked states. Since all 8 neighbors of the target are deadends, it is completely surrounded and impossible to reach.
Constraints
- 1 ≤ deadends.length ≤ 500
- deadends[i].length == 4
- target.length == 4
- target will not be in the list deadends
- target and deadends[i] consist of digits only
Editorial
Brute Force
Intuition
The most natural first instinct is to try sequences of moves using a depth-first search with backtracking. Think of it like navigating a maze by always picking one direction, going as far as you can, and then retracing your steps when you hit a wall.
From the starting code "0000", we have 8 possible moves: each of the 4 wheels can be turned either up or down by one slot. From each resulting state, we again have 8 moves, and so on.
A plain DFS falls into a trap here. It dives along one path until it happens to reach the target, and that first path can be thousands of turns long: on Example 1, the first path it finds is 2,230 turns long. Proving that nothing shorter exists would then mean trying every shorter path, far too many to finish. So we cap the depth instead. Iterative deepening runs the DFS with a depth limit of 1, then 2, then 3, and so on, never going deeper than the current limit. The first limit at which the DFS reaches the target is the minimum number of turns, because every smaller limit has already failed.
To avoid walking in circles (e.g., turning a wheel up and then straight back down), we keep a visited set of the states on the current path. Before visiting a state, we add it to the set; after fully exploring it, we remove it (backtracking) so other paths can still pass through it. We also check each state against the deadends set and prune immediately if a state is blocked.
One case is left: if the target cannot be reached at all, the limit would grow forever. So before deepening, we run a quick flood fill from "0000" that skips deadends. If it never reaches the target, we return -1 straight away.
Step-by-Step Explanation
Let's trace the code on Example 1: deadends = ["0201","0101","0102","1212","2002"], target = "0202". The DFS tries moves in the code's order: wheel 0 up, wheel 0 down, wheel 1 up, wheel 1 down, and so on.
Step 1: "0000" is not a deadend and is not the target.
Step 2: Flood fill from "0000", skipping deadends. It reaches "0202", so a path exists. Start deepening.
Step 3: Limit 1. The DFS tries the 8 neighbors of "0000": "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009". None is the target.
Step 4: Limits 2 to 5. The DFS explores every path of up to 5 turns, and none reaches "0202". The direct four-turn routes (wheel 1 up twice and wheel 3 up twice, in some order) all pass a deadend: one order hits "0201", four hit "0101" and one hits "0102".
Step 5: Limit 6. The DFS starts again from "0000" and takes "1000" first (wheel 0 up). It explores "2000" and gives up on it: from there "0202" is still 6 turns away, with only 4 left. It moves on to "1100", where "2100" and "0100" fail within the limit, and then to "1200". From "1200", the moves to "2200", "0200", "1300", "1210" and "1290" fail too, and turning wheel 3 up gives "1201".
Step 6: From "1201", turning wheel 0 up gives "2201", which fails; turning wheel 0 down gives "0201", a DEADEND, so it is skipped. After "1301", "1101", "1211" and "1291" fail, turning wheel 3 up gives "1202".
Step 7: From "1202", turning wheel 0 up gives "2202", but the limit is reached there. Turning wheel 0 down gives "0202": the TARGET, at depth 6.
Step 8: Return 6. Every limit below 6 failed, so 6 is the minimum. The path is "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202". Across the six passes, the DFS made 27,616 calls.
Iterative Deepening — DFS Under a Growing Depth Limit — Watch a depth-limited DFS run again and again with limits 1 to 6. Each pass backtracks at deadends and at the limit; the first limit that reaches the target is the answer.
Algorithm
- Place all deadends in a hash set for O(1) lookup
- If "0000" is a deadend, return -1; if the target is "0000", return 0
- Flood fill from "0000", skipping deadends; if the target is never reached, return -1
- For limit = 1, 2, 3, …, run a DFS from "0000" with depth = 0 and a visited set containing "0000":
- If the current state equals the target, the search succeeds
- If depth equals limit, stop exploring this branch
- For each of the 4 wheels, try turning it up (+1) and down (-1): if the new state is not in deadends and not in visited, add it to visited, recurse with depth + 1, then remove it (backtracking)
- Return the first limit at which the DFS reaches the target
Code
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
if (target == "0000") return 0;
// Step 1: flood fill from "0000". If it never reaches the target, return -1.
unordered_set<string> seen = {"0000"};
vector<string> pending = {"0000"};
while (!pending.empty()) {
string state = pending.back();
pending.pop_back();
for (const string& next : neighbors(state)) {
if (!dead.count(next) && !seen.count(next)) {
seen.insert(next);
pending.push_back(next);
}
}
}
if (!seen.count(target)) return -1;
// Step 2: DFS that never goes deeper than limit, for limit = 1, 2, 3, ...
unordered_set<string> visited = {"0000"};
int limit = 1;
while (!dfs("0000", target, dead, visited, 0, limit)) limit++;
return limit;
}
private:
vector<string> neighbors(const string& state) {
vector<string> result;
for (int i = 0; i < 4; i++) {
for (int delta : {1, -1}) {
string next = state;
next[i] = '0' + (state[i] - '0' + delta + 10) % 10;
result.push_back(next);
}
}
return result;
}
bool dfs(const string& state, const string& target, unordered_set<string>& dead,
unordered_set<string>& visited, int depth, int limit) {
if (state == target) return true;
if (depth == limit) return false;
for (const string& next : neighbors(state)) {
if (!dead.count(next) && !visited.count(next)) {
visited.insert(next);
bool found = dfs(next, target, dead, visited, depth + 1, limit);
visited.erase(next);
if (found) return true;
}
}
return false;
}
};class Solution:
def openLock(self, deadends: list[str], target: str) -> int:
dead = set(deadends)
if "0000" in dead:
return -1
if target == "0000":
return 0
def neighbors(state: str) -> list[str]:
result = []
for i in range(4):
d = int(state[i])
for delta in [1, -1]:
new_digit = (d + delta) % 10
result.append(state[:i] + str(new_digit) + state[i + 1:])
return result
# Step 1: flood fill from "0000". If it never reaches the target, return -1.
seen = {"0000"}
pending = ["0000"]
while pending:
state = pending.pop()
for new_state in neighbors(state):
if new_state not in seen and new_state not in dead:
seen.add(new_state)
pending.append(new_state)
if target not in seen:
return -1
# Step 2: DFS that never goes deeper than limit, for limit = 1, 2, 3, ...
def dfs(state: str, depth: int, limit: int, visited: set) -> bool:
if state == target:
return True
if depth == limit:
return False
for new_state in neighbors(state):
if new_state not in visited and new_state not in dead:
visited.add(new_state)
found = dfs(new_state, depth + 1, limit, visited)
visited.remove(new_state)
if found:
return True
return False
limit = 1
while not dfs("0000", 0, limit, {"0000"}):
limit += 1
return limitimport java.util.*;
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) return -1;
if (target.equals("0000")) return 0;
// Step 1: flood fill from "0000". If it never reaches the target, return -1.
Set<String> seen = new HashSet<>();
Deque<String> pending = new ArrayDeque<>();
seen.add("0000");
pending.push("0000");
while (!pending.isEmpty()) {
String state = pending.pop();
for (String next : neighbors(state)) {
if (!dead.contains(next) && !seen.contains(next)) {
seen.add(next);
pending.push(next);
}
}
}
if (!seen.contains(target)) return -1;
// Step 2: DFS that never goes deeper than limit, for limit = 1, 2, 3, ...
Set<String> visited = new HashSet<>();
visited.add("0000");
int limit = 1;
while (!dfs("0000", target, dead, visited, 0, limit)) limit++;
return limit;
}
private List<String> neighbors(String state) {
List<String> result = new ArrayList<>();
for (int i = 0; i < 4; i++) {
for (int delta : new int[]{1, -1}) {
char[] chars = state.toCharArray();
chars[i] = (char) ('0' + (chars[i] - '0' + delta + 10) % 10);
result.add(new String(chars));
}
}
return result;
}
private boolean dfs(String state, String target, Set<String> dead,
Set<String> visited, int depth, int limit) {
if (state.equals(target)) return true;
if (depth == limit) return false;
for (String next : neighbors(state)) {
if (!dead.contains(next) && !visited.contains(next)) {
visited.add(next);
boolean found = dfs(next, target, dead, visited, depth + 1, limit);
visited.remove(next);
if (found) return true;
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(N + 8^d), where N = 10^4 (total possible states) and d is the answer (the minimum number of turns)
The flood fill visits each of the N states at most once and checks 8 neighbors for each. A DFS limited to depth L explores every path of up to L turns from "0000" that avoids deadends and never revisits a state on its own path: at most 8 choices for the first turn and 7 for each later one, so O(8^L) paths. The passes for L = 1, 2, …, d add up to O(8^d), dominated by the last one. On Example 1, the full passes for limits 1 to 5 make 9, 63, 439, 2,993 and 20,515 calls, about 7 times more for each extra turn, so an answer of 20 (target "5555" with no deadend in the way) is far out of reach.
Space Complexity: O(N)
The flood fill's seen set and stack can hold up to N states. The DFS itself stores only the current path: its recursion depth and visited set never exceed d + 1 states. The deadends set uses O(D) space where D is the number of deadends.
Why This Approach Is Not Efficient
The DFS backtracking approach has fundamental flaws for finding the shortest path:
1. No shortest-path guarantee on first discovery. DFS dives deep into one direction before trying alternatives. Without a depth limit, its first path to the target on Example 1 is 2,230 turns long, although a path of length 6 existed all along, and confirming the shortest would mean trying every shorter path. Iterative deepening restores the guarantee, but only by searching again for every limit.
2. Exponential branching. Each state has 8 neighbors. At depth d, the DFS tree can have up to 8^d branches, and different paths keep arriving at the same states: on Example 1, the limit-5 pass alone makes 20,515 calls to cover the 672 states within 5 turns of "0000". The lock has only 10,000 states, yet an answer of just 6 already takes 27,616 DFS calls, and each extra turn in the answer multiplies the work by about 7.
3. Repeated work and backtracking. Every new limit starts over from "0000" and redoes all the shallower searches. Every dead end also means unwinding the recursion stack and undoing visited marks — the DFS is doing and then undoing work repeatedly.
The critical insight: Every turn costs exactly 1 move — this is an unweighted graph. For unweighted shortest-path problems, Breadth-First Search (BFS) is provably optimal: it explores all states at distance d before any state at distance d+1. The FIRST time BFS reaches the target, it has found the shortest path. No backtracking, no repeated passes, and each of the 10,000 states is visited at most once.
Optimal Approach - BFS (Breadth-First Search)
Intuition
Model the problem as a graph. Each of the 10,000 possible 4-digit codes ("0000" through "9999") is a node. Two nodes are connected by an edge if they differ in exactly one digit, and that digit differs by exactly 1 (with wrapping: '0' and '9' are adjacent). Deadends are nodes that we simply remove from the graph.
Now the problem becomes: find the shortest path from node "0000" to node "target" in this unweighted graph, avoiding removed nodes. The classic algorithm for shortest path in an unweighted graph is Breadth-First Search (BFS).
BFS explores nodes in order of their distance from the start:
- First, all nodes 1 turn away from "0000"
- Then, all nodes 2 turns away
- Then 3 turns, and so on
The moment we reach the target, we know the distance is minimal — because BFS guarantees every shorter distance was already checked. A plain DFS has no such guarantee, and iterative deepening gets it only by repeating the search for every depth; BFS gets it in a single pass.
Step-by-Step Explanation
Let's trace with deadends = ["0201","0101","0102","1212","2002"], target = "0202".
We show a subgraph of key states along the optimal path.
Step 1: Initialize. Place deadends in a set. Enqueue "0000". Mark visited. moves = 0.
Step 2: Level 0 — Dequeue "0000". Generate all 8 neighbors by turning each wheel ±1: {"1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"}. None is the target. Enqueue all. Mark visited.
Step 3: Level 0 complete. moves = 1. Queue has 8 states.
Step 4: Level 1 — Process "1000": neighbor "1100" is new, enqueue. Process "0100": neighbor "0101" is a DEADEND → skip! Process remaining Level 1 states.
Step 5: Level 1 complete. moves = 2. Among new states enqueued: "1100".
Step 6: Level 2 — Process "1100": neighbor "1200" is new, enqueue.
Step 7: Level 2 complete. moves = 3. "1200" is in the queue.
Step 8: Level 3 — Process "1200": neighbor "1201" is new, enqueue.
Step 9: Level 3 complete. moves = 4.
Step 10: Level 4 — Process "1201": neighbor "0201" is a DEADEND → skip! Neighbor "1202" is valid, enqueue.
Step 11: Level 4 complete. moves = 5.
Step 12: Level 5 — Process "1202": neighbor "0202" equals the TARGET! Return moves + 1 = 6.
Step 13: Path found: "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202". Total: 6 turns.
BFS — Level-by-Level Exploration of Lock States — Watch how BFS systematically explores all states at distance d before moving to distance d+1, guaranteeing the shortest path is found first.
Algorithm
- Place all deadends in a hash set for O(1) lookup
- If "0000" is a deadend, return -1 immediately
- If target is "0000", return 0
- Initialize a queue with "0000" and a visited set containing "0000"
- Set moves = 0
- While the queue is not empty:
a. Record current queue size (number of states at this BFS level)
b. For each state in this level:- Dequeue the state
- For each of 4 wheels, try turning up (+1) and down (-1):
- If the new state equals target, return moves + 1
- If not visited and not a deadend, mark visited and enqueue
c. Increment moves
- Queue empty and target not found → return -1
Code
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
if (target == "0000") return 0;
queue<string> q;
unordered_set<string> visited;
q.push("0000");
visited.insert("0000");
int moves = 0;
while (!q.empty()) {
int size = q.size();
for (int k = 0; k < size; k++) {
string state = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
for (int delta : {1, -1}) {
string next = state;
next[i] = '0' + (state[i] - '0' + delta + 10) % 10;
if (next == target) return moves + 1;
if (!dead.count(next) && !visited.count(next)) {
visited.insert(next);
q.push(next);
}
}
}
}
moves++;
}
return -1;
}
};from collections import deque
class Solution:
def openLock(self, deadends: list[str], target: str) -> int:
dead = set(deadends)
if "0000" in dead:
return -1
if target == "0000":
return 0
queue = deque(["0000"])
visited = {"0000"}
moves = 0
while queue:
size = len(queue)
for _ in range(size):
state = queue.popleft()
for i in range(4):
d = int(state[i])
for delta in [1, -1]:
new_digit = (d + delta) % 10
new_state = state[:i] + str(new_digit) + state[i + 1:]
if new_state == target:
return moves + 1
if new_state not in visited and new_state not in dead:
visited.add(new_state)
queue.append(new_state)
moves += 1
return -1import java.util.*;
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
if (dead.contains("0000")) return -1;
if (target.equals("0000")) return 0;
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer("0000");
visited.add("0000");
int moves = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
String state = queue.poll();
for (int i = 0; i < 4; i++) {
for (int delta : new int[]{1, -1}) {
char[] chars = state.toCharArray();
chars[i] = (char) ('0' + (chars[i] - '0' + delta + 10) % 10);
String next = new String(chars);
if (next.equals(target)) return moves + 1;
if (!dead.contains(next) && !visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
}
moves++;
}
return -1;
}
}Complexity Analysis
Time Complexity: O(N × D + D_set)
Where N = 10^4 = 10,000 (total possible 4-digit states), D = 8 (neighbors per state: 4 wheels × 2 directions), and D_set is the number of deadends.
Each of the N states is visited at most once, and for each we check 8 neighbors — this gives O(N × 8) = O(N) for the BFS. Building the deadends set costs O(D_set). The total is O(N + D_set), which is at most O(10,000 + 500) = O(10,500). This is extremely fast.
Space Complexity: O(N)
The visited set can hold up to N states. The queue can hold up to N states in the worst case. The deadends set holds D_set entries. Total space: O(N + D_set) = O(N).