The O(n) Club: Open the Lock (LeetCode 752) — When BFS Is Literally All You Need

The O(n) Club: Open the Lock (LeetCode 752) — When BFS Is Literally All You Need

⚡ TL;DR

You’ve got a 4-wheel lock (think: digital nightmare), each wheel spins 0–9 (and wraps, because of course it does). Each turn: spin one wheel up or down, no skipping and no magic keys. You start at ‘0000’, must not visit any deadends (trap codes), and want the shortest path to a target. Sound like a BFS problem? That’s because it absolutely is.

// Queue up BFS like it's 1999
Queue<String> q = new LinkedList<>();
Set<String> seen = new HashSet<>();
q.offer("0000");
seen.add("0000");
int moves = 0;
while (!q.isEmpty()) {
    for (int k = q.size(); k > 0; k--) {
        String code = q.poll();
        // ... neighbor code gen/check ...
    }
    moves++;
}

🧠 How Devs Usually Mess This Up

Every newbie’s first lock-picking attempt: “Should I use Dijkstra’s? Maybe a PriorityQueue!” 🎺 WRONGO. All moves are equal weight, so regular BFS is king. Oh, and forgetting to mark codes as visited? Enjoy your endless loop tour of digital purgatory. And if you handle wheel wrap-around like '9' + 1 = 10, you’ll wish for actual bolt cutters.

🔍 What’s Actually Going On

It’s a maze, but every “room” is a 4-digit code. From any room, eight doors: spin each wheel up or down. Some doors are bolted (the deadends). If you revisit rooms you’ve already seen, you’re just walking in circles, like a lost bot. BFS lets you surf each possible move, level-by-level, and guarantees you’ll find the shortest escape route before your patience deadlocks.

🛠️ PseudoCode

• Dump deadends into a Set: That way you can check danger faster than your CPU checks filenames.
• Edge check: If ‘0000’ is a deadend, just return -1 and go grab coffee. If the target is ‘0000’, congrats, you’re already out.
• BFS bootup: Add ‘0000’ to queue and mark it as visited.
• While you still have codes to try:
  • Pop a code from the queue. If it’s the target, return your move count (and flex your BFS skills).
  • If it’s a deadend, ignore it—no need to die twice.
  • For each wheel, try spinning up and spinning down (use modular arithmetic for ‘9’ to ‘0’ and ‘0’ to ‘9’).
  • If a new code hasn’t been visited and isn’t a deadend, toss it in the queue and mark it seen. Because if you don’t, someone will ask, “Why is this TLE’ing?” and you’ll have to lie.
• If you run out of codes: Return -1. Some locks just never open, contrary to what your local escape room guy tells you.

💻 The Code

import java.util.*;
 public class OpenLock {
    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 moves = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                String curr = queue.poll();
                if (curr.equals(target)) return moves;
                if (dead.contains(curr)) continue;
                for (int j = 0; j < 4; j++) {
                    char[] arr = curr.toCharArray();
                    // Spin wheel up
                    arr[j] = arr[j] == '9' ? '0' : (char)(arr[j] + 1);
                    String up = new String(arr);
                    if (!visited.contains(up) && !dead.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    // Spin wheel down
                    arr[j] = arr[j] == '0' ? '9' : (char)(arr[j] - 1);
                    String down = new String(arr);
                    if (!visited.contains(down) && !dead.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            moves++;
        }
        return -1;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• ‘0000’ in deadends? You’re locked out before you even start. Save your stack trace.
• Target is ‘0000’? Don’t move. Literally, print 0.
• Wrap-around fail: If you let ‘9’ become ’10’, you’re writing in base-FAIL.
• Visited state amnesia: Omit the visited set and call your recruiter—the infinite loop will outlast your patience.
• Complexity sanity check: 10,000 possible codes; in the worst world, you’ll see each one only once. That’s O(N), and N won’t eat your RAM unless you’re running this on a potato.

🧠 Interviewer Brain-Tattoo

“When every move costs the same, BFS is the Way, the Truth, and the Unlock.”