Open the Lock — Solution in Python, Java & C++
Open the Lock solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.
Open the Lock is a medium coding problem on arrays, strings and breadth-first search, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Breadth-First Search
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A lock has four circular wheels, each showing one of '0' … '9'. A wheel wraps around, so '9' turns to '0' and back. One move turns exactly one wheel by one notch.
The lock starts at "0000". If it ever shows one of the deadends, the wheels jam and it can never be turned again. Return the smallest number of moves that reaches target, or -1 if that is impossible.
Example 1
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: Via "0000" → "1000" → "1100" → "1200" → "1201" → "1202" → "0202"; the direct route runs into a deadend.
Example 2
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: Turn the last wheel down one notch.
Example 3
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: The target is walled in by deadends.
Constraints
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target is not in the list deadends.target and deadends[i] consist of digits only.
Hints for Open the Lock
Hint 1
There are only 10 000 possible readings, so the whole state space fits in memory.
Hint 2
Each reading has eight neighbours: four wheels, each turned up or down.
Hint 3
Breadth-first search from
"0000"gives the fewest moves.
How to solve Open the Lock
Treat each four-digit reading as a node with eight neighbours and run a breadth-first search from 0000. Deadends are simply nodes that are never entered.
Approach
- Mark the deadends. If
0000is one, the answer is-1at once. - BFS from
0000, generating the eight single-notch neighbours of each reading. - Skip deadends and readings already visited.
- Return the distance when the target is generated, or
-1if the queue runs dry.
Why it works
Every move has the same cost, which is exactly when BFS gives shortest distances — no priority queue is needed. Working with the reading as an integer 0 … 9999 and stepping a digit with (digit ± 1 + 10) % 10 keeps both the wrap-around and the visited array trivial. The graph is undirected, so the search covers everything reachable in at most 10 000 pops.
Complexity
- Time —
O(10^4 · 8) - Space —
O(10^4)
Pitfalls
"0000"being a deadend must be checked before the search starts.- A target of
"0000"answers 0. - The wheels wrap, so
'0'and'9'are neighbours.
Reference solution
Python
from typing import List
from collections import deque
def openLock(deadends: List[str], target: str) -> int:
blocked = [False] * 10000
for d in deadends:
blocked[int(d)] = True
goal = int(target)
if blocked[0]:
return -1
if goal == 0:
return 0
dist = [-1] * 10000
dist[0] = 0
q = deque([0])
powers = (1, 10, 100, 1000)
while q:
cur = q.popleft()
for p in powers:
digit = cur // p % 10
for step in (-1, 1):
nd = (digit + step) % 10
nxt = cur + (nd - digit) * p
if blocked[nxt] or dist[nxt] >= 0:
continue
dist[nxt] = dist[cur] + 1
if nxt == goal:
return dist[nxt]
q.append(nxt)
return -1Java
public static int openLock(String[] deadends, String target) {
boolean[] blocked = new boolean[10000];
for (String d : deadends) blocked[Integer.parseInt(d)] = true;
int goal = Integer.parseInt(target);
if (blocked[0]) return -1;
if (goal == 0) return 0;
int[] dist = new int[10000];
Arrays.fill(dist, -1);
dist[0] = 0;
int[] q = new int[10000];
int head = 0, tail = 0;
q[tail++] = 0;
int[] pow = { 1, 10, 100, 1000 };
while (head < tail) {
int cur = q[head++];
for (int p = 0; p < 4; p++) {
int digit = cur / pow[p] % 10;
for (int d = -1; d <= 1; d += 2) {
int nd = (digit + d + 10) % 10;
int next = cur + (nd - digit) * pow[p];
if (blocked[next] || dist[next] >= 0) continue;
dist[next] = dist[cur] + 1;
if (next == goal) return dist[next];
q[tail++] = next;
}
}
}
return -1;
}C++
int openLock(vector<string>& deadends, string target) {
vector<char> blocked(10000, 0);
for (auto& d : deadends) blocked[stoi(d)] = 1;
int goal = stoi(target);
if (blocked[0]) return -1;
if (goal == 0) return 0;
vector<int> dist(10000, -1), q;
dist[0] = 0;
q.push_back(0);
int pw[4] = { 1, 10, 100, 1000 };
for (size_t head = 0; head < q.size(); head++) {
int cur = q[head];
for (int p = 0; p < 4; p++) {
int digit = cur / pw[p] % 10;
for (int d = -1; d <= 1; d += 2) {
int nd = (digit + d + 10) % 10;
int next = cur + (nd - digit) * pw[p];
if (blocked[next] || dist[next] >= 0) continue;
dist[next] = dist[cur] + 1;
if (next == goal) return dist[next];
q.push_back(next);
}
}
}
return -1;
}JavaScript
var openLock = function(deadends, target) {
var i;
var blocked = [], dist = [];
for (i = 0; i < 10000; i++) { blocked.push(false); dist.push(-1); }
for (i = 0; i < deadends.length; i++) blocked[parseInt(deadends[i], 10)] = true;
var goal = parseInt(target, 10);
if (blocked[0]) return -1;
if (goal === 0) return 0;
dist[0] = 0;
var q = [0];
var head = 0;
var pow = [1, 10, 100, 1000];
while (head < q.length) {
var cur = q[head++];
for (var p = 0; p < 4; p++) {
var digit = Math.floor(cur / pow[p]) % 10;
for (var d = -1; d <= 1; d += 2) {
var nd = (digit + d + 10) % 10;
var next = cur + (nd - digit) * pow[p];
if (blocked[next] || dist[next] >= 0) continue;
dist[next] = dist[cur] + 1;
if (next === goal) return dist[next];
q.push(next);
}
}
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.