Open the Lock — Medium Problem & Solution

A lock has four circular wheels, each showing one of '0' … '9'. A wheel wraps around, so '9' turns to '0' and back.

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 <= 500
deadends[i].length == 4
target.length == 4
target is not in the list deadends.
target and deadends[i] consist of digits only.

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 0000 is one, the answer is -1 at 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 -1 if 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 -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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue