Domain 2MediumMEDIUM

Keys and Rooms

Determine if all rooms are reachable from room 0 using a graph traversal algorithm (BFS/DFS).

Domain: medium•Updated: 2026-09-02
#DFS#Graph Traversal#O(N + K) Time Complexity#O(N) Space Complexity

Problem Breakdown

We need to determine reachability in a directed graph where nodes represent rooms and edges represent keys. Room 0 is the starting node, initially unlocked. The goal is to verify if every room index from 0 to N-1 can be visited starting from 0. Since movement between unlocked rooms is free (once entered), we simply need to count how many unique nodes are reachable via a traversal algorithm like DFS or BFS.

  • Inputs: A list of lists (rooms) where each inner list contains integers representing keys found in that room.
  • Outputs: Boolean True if all rooms visited, else False.
  • Constraints: Room indices are valid [0, N-1]. Total number of keys is limited (3000).

Intuition

The problem models a graph connectivity check starting from node 0. Since we can traverse back and forth freely once a room key is obtained, the directionality doesn’t restrict reachability in terms of visiting nodes; it only dictates which new rooms become accessible upon entering one. This reduces to finding all nodes reachable from source 0. If the count of visited nodes equals total rooms (N), return True; otherwise False. A brute-force simulation is unnecessary as simple traversal suffices.

Approach

  1. Initialize a boolean array or set visited to track entered rooms, marking room 0 as visited immediately since it’s unlocked by default.
  2. Use a stack (for DFS) or queue (for BFS). Push room 0.
  3. While the traversal structure is not empty:
    • Pop/Dequeue current room index.
    • Iterate through keys in that room (rooms[current_room]).
    • For each key, if the target room hasn’t been visited yet, mark it as visited and push/enqueue to continue exploration from there.
  4. After traversal finishes (stack empty), check if all rooms are marked visited.

Complexity Analysis

  • Time Complexity: O(N+K)O(N + K), where NN is the number of rooms (len(rooms)) and KK is the total number of keys across all lists. Each room is pushed onto the stack at most once (O(N)O(N)), and each key is inspected exactly once during neighbor processing (O(K)O(K)). The final check sum(visited) takes O(N)O(N), keeping overall complexity linear relative to input size representation.
  • Space Complexity: O(N)O(N). We store a visited array of size NN and the stack/queue can hold at most NN elements in the worst case (e.g., star graph or line).

Solution

def canVisitAllRooms(rooms):
    n = len(rooms)
    
    # Track visited rooms; start with room 0 unlocked
    visited = [False] * n
    visited[0] = True
    
    stack = [0]
    
    while stack:
        current_room = stack.pop()
        
        for key in rooms[current_room]:
            if not visited[key]:
                visited[key] = True
                stack.append(key)
                
    # Return true only if we have marked every room as reachable
    return sum(visited) == n

# Example usage:
# print(canVisitAllRooms([[1],[2],[3],[]]))  # Output: True
# print(canVisitAllRooms([[1,3],[3,0,1],[2],[0]]))  # Output: False

Edge Cases Handled

  • Single Room (N=1): The loop processes room 0, stack empties. sum(visited) is 1, which equals n. Returns True. Correctly handles the case where no keys are needed to enter all rooms (since there’s only one).
  • No Keys in Start Room: If room 0 has an empty list and N>1N > 1, stack empties immediately. Visited count is 1, which does not equal n. Returns False. Correctly identifies unreachable rooms.
  • Cycles/Backtracking: The visited check prevents re-adding a room to the stack if it has already been entered, preventing infinite loops in cyclic graphs and ensuring linear time complexity relative to edges.