Keys and Rooms

medium graph dfs

Problem

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room. Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length.

Inputrooms = [[1,3],[3,0,1],[2],[0]]

Outputfalse

Room 2 is unreachable — no key for it appears in any room you can enter.

rooms (e.g. "1,3; 3,0,1; 2; 0")

def can_visit_all_rooms(rooms):
    seen = [False] * len(rooms)
    stack = [0]; seen[0] = True
    while stack:
        u = stack.pop()
        for v in rooms[u]:
            if not seen[v]:
                seen[v] = True; stack.append(v)
    return all(seen)

function canVisitAllRooms(rooms) {
  const seen = new Array(rooms.length).fill(false);
  const stack = [0]; seen[0] = true;
  while (stack.length) {
    const u = stack.pop();
    for (const v of rooms[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
  }
  return seen.every(Boolean);
}

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); seen[0] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : rooms.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
        }
        for (boolean s : seen) if (!s) return false;
        return true;
    }
}

bool canVisitAllRooms(vector<vector<int>>& rooms) {
    vector<bool> seen(rooms.size(), false);
    stack<int> st;
    st.push(0); seen[0] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int v : rooms[u]) if (!seen[v]) { seen[v] = true; st.push(v); }
    }
    for (bool s : seen) if (!s) return false;
    return true;
}

Explanation

Think of rooms as nodes and the keys inside a room as edges to other rooms. The question "can I reach every room starting from room 0?" is just a graph traversal followed by checking that nothing was left unvisited.

We use a DFS with an explicit stack. A seen array tracks which rooms we've entered. We push room 0, mark it seen, then repeatedly pop a room and look at the keys it holds.

For each key v in the popped room, if room v hasn't been seen yet, we mark it seen and push it onto the stack to explore later. Marking before pushing prevents adding the same room twice.

When the stack empties, we've reached everything reachable from room 0. The answer is simply whether every entry in seen is true — all(seen).

Example: rooms = [[1,3],[3,0,1],[2],[0]]. From 0 we open 1 and 3; room 1's keys lead nowhere new beyond what's seen. No reachable room ever holds a key for room 2, so seen[2] stays false and the answer is false.

Time: O(V + E) Space: O(V)