Open the Lock

Medium Graphs BFS for shortest path Original on LeetCode

Open the Lock is a medium graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (bidirectional bfs), runs in O(10⁴ · 4 · 2 + d) time and O(10⁴ + d) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs from the start up.

Problem

A combination lock has four wheels, each showing a digit from 0 to 9. One move turns a single wheel up or down by one step, and the wheels wrap around: 9 turns up to 0 and 0 turns down to 9. The lock starts at "0000".

You are given a list deadends of codes that jam the lock: if the wheels ever show one of them, the lock is stuck for good. Return the fewest moves needed to make the lock show target without ever passing through a dead end, or -1 if that is impossible.

Examples

Example 1

Input
deadends = ["0001", "0009"], target = "0002"
Output
4
Why
Both one-turn routes on the last wheel are blocked, so go around: 0000 → 0100 → 0101 → 0102 → 0002.

Example 2

Input
deadends = ["5555"], target = "9090"
Output
2
Why
Turning wheels 1 and 3 backward once each (0 → 9) reaches 9090.

Example 3

Input
deadends = ["1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"], target = "3333"
Output
-1
Why
Every code one turn away from 0000 is a dead end, so the lock cannot move at all.

Constraints

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4 and target.length == 4
  • deadends[i] and target contain only digits.
  • target is not in deadends.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
BFS from the startO(10⁴ · 4 · 2 + d)O(10⁴ + d)
Optimal (bidirectional BFS)O(10⁴ · 4 · 2 + d)O(10⁴ + d)

1BFS from the start

TimeO(10⁴ · 4 · 2 + d)At most 10,000 codes are dequeued, each generating 8 neighbours of length 4; d is the number of dead ends to load.
SpaceO(10⁴ + d)The visited set and the queue hold at most every code plus the dead ends.

Search outward from 0000 one turn at a time. Put the dead ends in the visited set from the beginning so they are never entered. The level at which the target is first popped is the answer.

  1. If 0000 is a dead end, return -1.
  2. Put all dead ends and 0000 into visited; queue = [0000]; turns = 0.
  3. Process the queue level by level. If a code equals target, return turns.
  4. For each of its 8 neighbours not yet visited, mark it and enqueue it. Increment turns after each level.
  5. If the queue empties, return -1.
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> visited = new HashSet<>(Arrays.asList(deadends));
        if (visited.contains("0000")) return -1;
        visited.add("0000");
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("0000");
        int turns = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                String cur = queue.poll();
                if (cur.equals(target)) return turns;
                for (String nb : neighbours(cur)) {
                    if (visited.add(nb)) queue.offer(nb);
                }
            }
            turns++;
        }
        return -1;
    }

    private List<String> neighbours(String code) {
        List<String> out = new ArrayList<>();
        char[] c = code.toCharArray();
        for (int i = 0; i < 4; i++) {
            char orig = c[i];
            c[i] = (char) ('0' + (orig - '0' + 1) % 10);
            out.add(new String(c));
            c[i] = (char) ('0' + (orig - '0' + 9) % 10);
            out.add(new String(c));
            c[i] = orig;
        }
        return out;
    }
}

2Optimal (bidirectional BFS)

TimeO(10⁴ · 4 · 2 + d)Same worst case as one BFS, but in practice each search only reaches about half the depth, which touches far fewer codes.
SpaceO(10⁴ + d)The visited set and the two frontier sets.

Grow one frontier from 0000 and another from the target, always expanding the smaller one. The moment a newly generated code lies in the opposite frontier, the two searches have met and the path length is the number of levels expanded so far plus one.

  1. If target is 0000 return 0; if 0000 is a dead end return -1.
  2. visited = dead ends + {0000, target}; front = {0000}; back = {target}; turns = 0.
  3. While both sets are non-empty: swap them if front is larger than back.
  4. Build next from every code in front: for each neighbour, if it is in back return turns + 1; else if it is unvisited, mark it and add it to next.
  5. Set front = next and turns++. If a frontier empties, return -1.
class Solution {
    public int openLock(String[] deadends, String target) {
        if (target.equals("0000")) return 0;
        Set<String> visited = new HashSet<>(Arrays.asList(deadends));
        if (visited.contains("0000")) return -1;
        visited.add("0000");
        visited.add(target);
        Set<String> front = new HashSet<>(), back = new HashSet<>();
        front.add("0000");
        back.add(target);
        int turns = 0;
        while (!front.isEmpty() && !back.isEmpty()) {
            if (front.size() > back.size()) {
                Set<String> tmp = front;
                front = back;
                back = tmp;
            }
            Set<String> next = new HashSet<>();
            for (String cur : front) {
                char[] c = cur.toCharArray();
                for (int i = 0; i < 4; i++) {
                    char orig = c[i];
                    for (int delta : new int[] { 1, 9 }) {
                        c[i] = (char) ('0' + (orig - '0' + delta) % 10);
                        String nb = new String(c);
                        if (back.contains(nb)) return turns + 1;
                        if (visited.add(nb)) next.add(nb);
                    }
                    c[i] = orig;
                }
            }
            front = next;
            turns++;
        }
        return -1;
    }
}

Edge cases to test

  • The start 0000 is itself a dead end: the answer is -1
  • The target is 0000: the answer is 0
  • Wrap-around: going from 0 to 9 is one turn
  • The target is reachable only by a detour around dead ends

Hints

Hint 1

Think of the 10,000 codes as nodes. Each code has 8 neighbours: each of 4 wheels turned up or down by one.

Hint 2

All moves cost one turn, so the fewest turns is a breadth-first search distance. Dead ends are nodes you may never enter.

Hint 3

To shrink the search, run BFS from both the start and the target and stop when the two frontiers touch.

FAQ

What is the best time complexity for Open the Lock?

Optimal (bidirectional BFS) runs in O(10⁴ · 4 · 2 + d) time and O(10⁴ + d) extra space. Same worst case as one BFS, but in practice each search only reaches about half the depth, which touches far fewer codes.

Which pattern does Open the Lock use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Open the Lock?

Yes. BFS from the start takes O(10⁴ · 4 · 2 + d) time and O(10⁴ + d) space. Search outward from 0000 one turn at a time.

Which edge cases should I test for Open the Lock?

The start 0000 is itself a dead end: the answer is -1; The target is 0000: the answer is 0; Wrap-around: going from 0 to 9 is one turn; The target is reachable only by a detour around dead ends.