Open the Lock

Medium
939.

Open the Lock

Open the Lock is a medium coding problem on arrays, strings and breadth-first search, asked in Amazon, Google and Uber interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function(deadends, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Open the Lock

  1. Hint 1

    There are only 10 000 possible readings, so the whole state space fits in memory.

  2. Hint 2

    Each reading has eight neighbours: four wheels, each turned up or down.

  3. 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

  1. Mark the deadends. If 0000 is one, the answer is -1 at once.
  2. BFS from 0000, generating the eight single-notch neighbours of each reading.
  3. Skip deadends and readings already visited.
  4. 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

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings