The O(n) Club: Keys and Rooms—How to Unlock a Mansion Without Losing Your Mind (or Your Java Stack)

The O(n) Club: Keys and Rooms—How to Unlock a Mansion Without Losing Your Mind (or Your Java Stack)

⚡ TL;DR

You wake up in room 0 of a suspiciously spacious mansion. Each room may have keys to other rooms. Can you actually visit every room—or will you wander until the cleaning robot finds your bones? Brute force means randomly running around, forgetting which rooms you’ve seen, and getting stuck in ghostly circles.

// Brute force (get ready to confuse your interviewer!)
boolean canVisitAllRooms(List<List<Integer>> rooms) {
    return dfs(rooms, 0, new HashSet<>());
}
// Where dfs... never mind, let's get practical.

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Picture every room as a node. Each key is directed edge—once you visit a room, you claim its keys and expand your empire of unlocked doors. It’s literally checking graph reachability: starting from node 0, can you reach every node? It’s more organized snooping than actual exploration.
You can use DFS (with a Stack) or BFS (with a Queue), but the secret sauce is only treading through rooms you haven’t seen yet. Explore with what’s in your hand—don’t teleport based on someone else’s optimism.

🛠️ PseudoCode

• Step 1: Create boolean[] visited to track entered rooms.
  boolean[] visited = new boolean[rooms.size()];
• Step 2: Grab a stack (DFS) and push room 0.
  Stack<Integer> stack = new Stack<>(); stack.push(0);
• Step 3: While the stack isn’t empty, pop a room.
  while (!stack.isEmpty()) { int current = stack.pop(); ... }
• Step 4: Mark the room as visited (don’t shake hands twice). For each key found, if it leads somewhere new, push it on the stack.
  for (int key : rooms.get(current)) if (!visited[key]) stack.push(key);
• Step 5: At the end, check if your visited[] is all true. If you missed even one, time to file a haunted mansion bug.

💻 The Code

public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    int n = rooms.size();
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    while (!stack.isEmpty()) {
        int room = stack.pop();
        if (visited[room]) continue;
        visited[room] = true;
        for (int key : rooms.get(room)) {
            if (!visited[key]) stack.push(key);
        }
    }
    for (boolean seen : visited) if (!seen) return false;
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Case: Only room 0 has no keys—fastest exit in interview history.
• Disconnected Rooms: Got a room and the only key is inside that locked room? Congrats on inventing a Schrödinger’s office.
• Redundant Visits: Unlocking the same room again is a sign you’re haunted (or not using visited[] properly).
• Performance: Time is O(rooms + keys), space is O(rooms), which means you can solve this well before your coffee gets cold (unless your mansion has 1,000,000 rooms… in which case: run).
• Recursion Stack Woes: Don’t get brave with recursion during interviews. Go iterative, unless you want Java to throw a tantrum.

🧠 Interviewer Brain-Tattoo

“Don’t bring a Bazooka to a keyhole—track your path, use what you have, and remember: graph traversal is just organized snooping with a badge.”