Open the Lock

MediumGraph BFS · Bidirectional BFS🧩 Graph BFS LeetCode #752 ↗Updated Oct 30, 2026

Problem

A lock has 4 wheels, each showing a digit 0–9, and starts at "0000". One move turns a single wheel one notch up or down (wrapping 9↔0). If the lock ever shows a code in deadends it jams. Return the minimum number of moves to show target, or -1 if impossible.

Inputdeadends = ["0201","0101","0102","1212","2002"], target = "0202"Output6

Inputdeadends = ["8888"], target = "0009"Output1

Inputdeadends = ["0000"], target = "8888"Output-1

1 ≤ deadends.length ≤ 500 · every code has exactly 4 digits · target is not in deadends

Try it yourself

Java

class Solution {
    public int openLock(String[] deadends, String target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The 10⁴ codes are nodes of an unweighted graph with 8 neighbours each, so the shortest move count is a plain BFS. Searching from both ends at once (bidirectional BFS) meets in the middle and explores far fewer codes.

PatternGraph BFS

Instinct Minimum moves, fewest steps or shortest transformation where every step costs the same: spread outward level by level with a queue.

Memory hack Ripples in a pond: every ring is one step farther, so the first ring that touches the target is the answer.

Open the Graph BFS guide →

Approaches

Brute ForceRepeated Relaxation (Bellman-Ford Style)

Time O(V·E)Space O(V)

Keep dist[code], start with dist[0000] = 0, and sweep all 10⁴ codes repeatedly, improving every neighbour via dist[s] + 1, until a full sweep changes nothing. It is correct for any graph but ignores that every edge weighs 1. Here V = 10⁴, E = 8V.

Java

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;
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[10000];
    Arrays.fill(dist, INF);
    dist[0] = 0;
    boolean changed = true;
    while (changed) {                  // sweep until nothing improves
        changed = false;
        for (int s = 0; s < 10000; s++) {
            if (dist[s] == INF) continue;
            for (int p = 1; p <= 1000; p *= 10) {
                int digit = s / p % 10;
                for (int step : new int[]{1, 9}) {   // +1 or -1 modulo 10
                    int next = s + ((digit + step) % 10 - digit) * p;
                    if (!dead[next] && dist[s] + 1 < dist[next]) {
                        dist[next] = dist[s] + 1;
                        changed = true;
                    }
                }
            }
        }
    }
    int goal = Integer.parseInt(target);
    return dist[goal] == INF ? -1 : dist[goal];
}

Simple and correct, but may sweep the whole state space many times.

BetterLevel-Order BFS on Strings

Time O(V·w² + D)Space O(V + D)

BFS from "0000": the first time a code is dequeued, its level is its shortest distance. Each code generates its 8 neighbours by rolling one wheel; deadends and already-seen codes are skipped. w = 4 wheels, D = number of deadends.

Java

public int openLock(String[] deadends, String target) {
    Set<String> blocked = new HashSet<>(Arrays.asList(deadends));
    if (blocked.contains("0000")) return -1;
    Set<String> seen = new HashSet<>();
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("0000");
    seen.add("0000");
    for (int moves = 0; !queue.isEmpty(); moves++) {
        for (int size = queue.size(); size > 0; size--) {
            String cur = queue.poll();
            if (cur.equals(target)) return moves;
            char[] w = cur.toCharArray();
            for (int i = 0; i < 4; i++) {
                char orig = w[i];
                for (int step : new int[]{1, 9}) {
                    w[i] = (char) ('0' + (orig - '0' + step) % 10);
                    String next = new String(w);
                    if (!blocked.contains(next) && seen.add(next)) queue.offer(next);
                }
                w[i] = orig;
            }
        }
    }
    return -1;
}

Visits each code once; string building and hashing add a constant-factor cost.

OptimalBidirectional BFS on Integer Codes

Time O(V·w + D)Space O(V)

Grow one BFS from 0000 and one from target, always expanding the smaller frontier by a full level. The first time a new code is already known to the other side, the two half-paths join into a shortest path. Codes are ints, so neighbours are pure arithmetic.

Java

public int openLock(String[] deadends, String target) {
    boolean[] dead = new boolean[10000];
    for (String d : deadends) dead[Integer.parseInt(d)] = true;
    int goal = Integer.parseInt(target);
    if (dead[0] || dead[goal]) return -1;
    if (goal == 0) return 0;
    int[] fromStart = new int[10000], fromGoal = new int[10000];
    Arrays.fill(fromStart, -1);
    Arrays.fill(fromGoal, -1);
    fromStart[0] = 0;
    fromGoal[goal] = 0;
    Deque<Integer> qs = new ArrayDeque<>(List.of(0)), qg = new ArrayDeque<>(List.of(goal));
    while (!qs.isEmpty() && !qg.isEmpty()) {
        boolean startSide = qs.size() <= qg.size();   // grow the smaller frontier
        Deque<Integer> q = startSide ? qs : qg;
        int[] mine = startSide ? fromStart : fromGoal;
        int[] other = startSide ? fromGoal : fromStart;
        for (int size = q.size(); size > 0; size--) {
            int cur = q.poll();
            for (int p = 1; p <= 1000; p *= 10) {
                int digit = cur / p % 10;
                for (int step : new int[]{1, 9}) {
                    int next = cur + ((digit + step) % 10 - digit) * p;
                    if (dead[next] || mine[next] != -1) continue;
                    if (other[next] != -1) return mine[cur] + 1 + other[next];
                    mine[next] = mine[cur] + 1;
                    q.offer(next);
                }
            }
        }
    }
    return -1;
}

Same worst case, but typically explores a small fraction of the 10⁴ codes.

Pro tip

Encoding a code as an int and using (digit + 9) % 10 for “minus one” avoids negative modulo bugs and string allocation entirely.

At a glance

Level	Approach	Time	Space
Brute Force	Repeated Relaxation (Bellman-Ford Style)	`O(V·E)`	`O(V)`
Better	Level-Order BFS on Strings	`O(V·w² + D)`	`O(V + D)`
Optimal	Bidirectional BFS on Integer Codes	`O(V·w + D)`	`O(V)`

Common pitfalls

Not checking whether "0000" itself is a deadend — answer must be -1.
Wrap-around: 0 - 1 must become 9, not -1 (add 9 instead of subtracting 1).
Marking codes visited when dequeued instead of when enqueued — duplicates blow up the queue.

Interview tips

Say “implicit graph: states are codes, edges are single-wheel turns” up front.
Treat deadends as pre-visited nodes — one array handles both.
Offer bidirectional BFS as the follow-up once plain BFS is on the board.

Pattern

BFS on an implicit state graph → minimum number of unit-cost moves between two configurations.

My notes saved in this browser