Open the Lock

NeetCode: Open the Lock · LeetCode: 752. Open the Lock · Difficulty: Medium

A lock has four circular wheels of digits 0-9 and starts at "0000". One move turns one wheel by one step (9 wraps to 0 and vice versa). You are given deadends, states that jam the lock, and a target. Return the minimum number of moves to reach target, or -1 if impossible.

Example

Text

Input:  deadends = ["0201","0101","0102","1212","2002"], target = "0202"    Output: 6
Input:  deadends = ["8888"], target = "0009"                                Output: 1
Input:  deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"    Output: -1

The 10000 lock states are vertices; each state has 8 neighbours (4 wheels, 2 directions). That makes it a shortest path in an unweighted graph.

The solutions turn each state string into an int with Integer.parseInt, so "0202" becomes 202. The wheel digits are then read with / and % by powers of ten.

Brute force: keep relaxing all states until stable

Store the best known distance for every state, start with dist[0000] = 0, and repeatedly sweep over all 10000 states, improving each neighbour's distance through non-deadend states. Stop when a full sweep changes nothing. Every sweep touches all states even though most are irrelevant, and the number of sweeps depends on the order in which states are processed.

Integer.MAX_VALUE marks "not reached". Unreached states are skipped before dist[s] + 1 is computed, so the addition cannot overflow.

Java

import java.util.Arrays;

class Solution {
    private int[] neighbors(int s) {
        int[] out = new int[8];
        int k = 0;
        int pow = 1;
        for (int wheel = 0; wheel < 4; wheel++) {
            int d = s / pow % 10;
            int[] digits = {(d + 1) % 10, (d + 9) % 10};
            for (int nd : digits) {
                out[k++] = s - d * pow + nd * pow;
            }
            pow *= 10;
        }
        return out;
    }

    public int openLock(String[] deadends, String target) {
        boolean[] dead = new boolean[10000];
        for (String d : deadends) {
            dead[Integer.parseInt(d)] = true;
        }
        if (dead[0]) {
            return -1;
        }
        int goal = Integer.parseInt(target);
        int[] dist = new int[10000];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int s = 0; s < 10000; s++) {
                if (dist[s] == Integer.MAX_VALUE) {
                    continue;
                }
                for (int t : neighbors(s)) {
                    if (!dead[t] && dist[s] + 1 < dist[t]) {
                        dist[t] = dist[s] + 1;
                        changed = true;
                    }
                }
            }
        }
        return dist[goal] == Integer.MAX_VALUE ? -1 : dist[goal];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
        System.out.println(s.openLock(new String[]{"8888"}, "0009"));
        String[] dead = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
        System.out.println(s.openLock(dead, "8888"));
        System.out.println(s.openLock(new String[]{"0000"}, "8888"));
        System.out.println(s.openLock(new String[]{}, "0000"));
    }
}

Output

Time: O(S * 8 * P) for S = 10^4 states and P sweeps (P is at most the answer plus one). Space: O(S).

Optimal: breadth-first search from "0000"

BFS visits states in order of distance, so the first time it dequeues the target the distance is minimal, and it never explores states farther than the answer. Deadends are marked as already visited so they are never entered; if 0000 itself is a deadend the answer is -1. The queue is an ArrayDeque<int[]> of {state, moves} pairs.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private int[] neighbors(int s) {
        int[] out = new int[8];
        int k = 0;
        int pow = 1;
        for (int wheel = 0; wheel < 4; wheel++) {
            int d = s / pow % 10;
            int[] digits = {(d + 1) % 10, (d + 9) % 10};
            for (int nd : digits) {
                out[k++] = s - d * pow + nd * pow;
            }
            pow *= 10;
        }
        return out;
    }

    public int openLock(String[] deadends, String target) {
        boolean[] seen = new boolean[10000];
        for (String d : deadends) {
            seen[Integer.parseInt(d)] = true;
        }
        if (seen[0]) {
            return -1;
        }
        int goal = Integer.parseInt(target);
        seen[0] = true;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == goal) {
                return cur[1];
            }
            for (int t : neighbors(cur[0])) {
                if (!seen[t]) {
                    seen[t] = true;
                    queue.add(new int[]{t, cur[1] + 1});
                }
            }
        }
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
        System.out.println(s.openLock(new String[]{"8888"}, "0009"));
        String[] dead = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
        System.out.println(s.openLock(dead, "8888"));
        System.out.println(s.openLock(new String[]{"0000"}, "8888"));
        System.out.println(s.openLock(new String[]{}, "0000"));
    }
}

Output

The case target = "0000" with no deadends returns 0 on the first dequeue. A deadend that equals the target is marked seen, so the target is never enqueued and the answer is -1. Time: O(S * 8) with S = 10^4, which is a constant for a four-wheel lock. Space: O(S).