Open the Lock

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonGoogle

Problem Description

You have a lock with 4 circular wheels. Each wheel has the values '0' to '9'. The lock starts at "0000". Each move turns one wheel up or down one step.

You are given a list of deadends. If the lock reaches any of these combinations, the lock can no longer turn. Return the minimum number of turns to reach the target, or -1 if it is impossible.

Examples

Example 1:

Input: deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202” Output: 6

Example 2:

Input: deadends = [“8888”], target = “0009” Output: 1

Example 3:

Input: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888” Output: -1

Constraints

1 ≤ deadends.length ≤ 500
deadends[i].length == 4
target.length == 4
target will not be in deadends
target and deadends[i] consist of digits only

BFS on the State Space of Combinations

The lock has 10^4 = 10,000 possible states. Each state has 8 neighbors (4 wheels × 2 directions). BFS from "0000" finds the shortest path (fewest turns) to target.

Use a set for deadends and a visited set. Each BFS level corresponds to one turn. The first time BFS reaches target, return the level count.

Solution: BFS

import 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 turns = 0;

        while (!queue.isEmpty()) {
            turns++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                for (String next : getNeighbors(curr)) {
                    if (next.equals(target)) return turns;
                    if (!visited.contains(next) && !dead.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
        }
        return -1;
    }

    private List<String> getNeighbors(String s) {
        List<String> neighbors = new ArrayList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < 4; i++) {
            char orig = chars[i];
            // turn up
            chars[i] = (char)((orig - '0' + 1) % 10 + '0');
            neighbors.add(new String(chars));
            // turn down
            chars[i] = (char)((orig - '0' + 9) % 10 + '0');
            neighbors.add(new String(chars));
            chars[i] = orig; // restore
        }
        return neighbors;
    }
}

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"}
        turns = 0

        while queue:
            turns += 1
            for _ in range(len(queue)):
                curr = queue.popleft()
                for i in range(4):
                    digit = int(curr[i])
                    for delta in (1, -1):
                        new_digit = (digit + delta) % 10
                        next_s = curr[:i] + str(new_digit) + curr[i+1:]
                        if next_s == target:
                            return turns
                        if next_s not in visited and next_s not in dead:
                            visited.add(next_s)
                            queue.append(next_s)

        return -1

#include <string>
#include <queue>
#include <unordered_set>
#include <vector>

class Solution {
public:
    int openLock(std::vector<std::string>& deadends, std::string target) {
        std::unordered_set<std::string> dead(deadends.begin(), deadends.end());
        if (dead.count("0000")) return -1;
        if (target == "0000") return 0;

        std::queue<std::string> q;
        std::unordered_set<std::string> visited;
        q.push("0000");
        visited.insert("0000");
        int turns = 0;

        while (!q.empty()) {
            turns++;
            int sz = q.size();
            while (sz--) {
                std::string curr = q.front(); q.pop();
                for (int i = 0; i < 4; i++) {
                    for (int delta : {1, -1}) {
                        std::string next = curr;
                        next[i] = (char)(((curr[i] - '0') + delta + 10) % 10 + '0');
                        if (next == target) return turns;
                        if (!visited.count(next) && !dead.count(next)) {
                            visited.insert(next);
                            q.push(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
};

Complexity Analysis:

Time Complexity: O(10^4 * 4 * 2) = O(80,000). There are 10,000 possible lock states, each with 8 neighbors.
Space Complexity: O(10^4) for visited and the queue.

Where it breaks: if "0000" is in deadends, return -1 immediately before even creating the queue. If you don’t check this, you’d add "0000" to visited but it’s also in deadends, which can cause issues depending on implementation.

Common Mistakes

Not checking if "0000" is a deadend upfront. The start state itself could be blocked.
Wrapping digits: 9 + 1 = 0 and 0 - 1 = 9. The modulo % 10 handles this, but (digit - 1 + 10) % 10 must use +10 to avoid negative modulo in some languages.
Checking target membership after adding to queue vs. before. Check when you generate the neighbor to return early without an extra queue pop.