Keys and Rooms

This question is asked by Amazon. Given N distinct rooms that are locked, we want to know if you can unlock and visit every room. Each room has a list of keys in it that allows you to unlock and visit other rooms. We start with room 0 being unlocked. Return whether or not we can visit every room.

Note: You can only visit a room if you have a key to it. Starting from room 0, you collect keys from visited rooms to unlock other rooms.

Example(s)

Example 1:

Input: rooms = [[1], [2], []]
Output: true
Explanation:
- Start at room 0 (unlocked)
- Room 0 has key to room 1
- Visit room 1, get key to room 2
- Visit room 2 (no keys, but we've visited all rooms)
We can visit all 3 rooms: 0, 1, 2

Example 2:

Input: rooms = [[1, 2], [2], [0], []]
Output: false
Explanation:
- Start at room 0 (unlocked)
- Room 0 has keys to rooms 1 and 2
- Visit room 1, get key to room 2 (already have it)
- Visit room 2, get key to room 0 (already visited)
- Room 3 has no keys and we can't reach it
We cannot visit room 3.

Example 3:

Input: rooms = [[1], [2], [3], []]
Output: true
Explanation:
- Room 0 → Room 1 → Room 2 → Room 3
- Can visit all rooms sequentially

Solution

The solution uses BFS or DFS to traverse from room 0:

1. Start from room 0: Room 0 is initially unlocked
2. Collect keys: When visiting a room, collect all keys from it
3. Visit unlocked rooms: Use keys to visit new rooms
4. Track visited: Keep track of which rooms have been visited
5. Check completion: After traversal, check if all rooms were visited

JavaScript Solution

JavaScript Solution - BFS

/**
* Check if all rooms can be visited
* @param {number[][]} rooms - Array where rooms[i] contains keys to other rooms
* @return {boolean} - True if all rooms can be visited
*/
function canVisitAllRooms(rooms) {
const n = rooms.length;
const visited = new Set();
const queue = [0]; // Start with room 0
visited.add(0);

// BFS to visit all reachable rooms
while (queue.length > 0) {
  const currentRoom = queue.shift();
  
  // Collect keys from current room
  for (const key of rooms[currentRoom]) {
    if (!visited.has(key)) {
      visited.add(key);
      queue.push(key);
    }
  }
}

// Check if we visited all rooms
return visited.size === n;
}

// Test cases
console.log('Example 1:', canVisitAllRooms([[1], [2], []])); // true
console.log('Example 2:', canVisitAllRooms([[1, 2], [2], [0], []])); // false
console.log('Example 3:', canVisitAllRooms([[1], [2], [3], []])); // true
console.log('Test 4:', canVisitAllRooms([[1, 3], [3, 0, 1], [2], [0]])); // false

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - BFS

from typing import List
from collections import deque

def can_visit_all_rooms(rooms: List[List[int]]) -> bool:
  """
  Check if all rooms can be visited
  
  Args:
      rooms: List where rooms[i] contains keys to other rooms
      
  Returns:
      bool: True if all rooms can be visited
  """
  n = len(rooms)
  visited = set()
  queue = deque([0])  # Start with room 0
  visited.add(0)
  
  # BFS to visit all reachable rooms
  while queue:
      current_room = queue.popleft()
      
      # Collect keys from current room
      for key in rooms[current_room]:
          if key not in visited:
              visited.add(key)
              queue.append(key)
  
  # Check if we visited all rooms
  return len(visited) == n

# Test cases
print('Example 1:', can_visit_all_rooms([[1], [2], []]))  # True
print('Example 2:', can_visit_all_rooms([[1, 2], [2], [0], []]))  # False
print('Example 3:', can_visit_all_rooms([[1], [2], [3], []]))  # True
print('Test 4:', can_visit_all_rooms([[1, 3], [3, 0, 1], [2], [0]]))  # False

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (DFS)

Here's a DFS version:

JavaScript DFS

/**
 * DFS version
 */
function canVisitAllRoomsDFS(rooms) {
  const n = rooms.length;
  const visited = new Set();
  
  function dfs(room) {
    if (visited.has(room)) {
      return;
    }
    
    visited.add(room);
    
    // Visit all rooms we can unlock from here
    for (const key of rooms[room]) {
      dfs(key);
    }
  }
  
  // Start DFS from room 0
  dfs(0);
  
  // Check if we visited all rooms
  return visited.size === n;
}

Python DFS

def can_visit_all_rooms_dfs(rooms: List[List[int]]) -> bool:
    """
    DFS version
    """
    n = len(rooms)
    visited = set()
    
    def dfs(room: int):
        if room in visited:
            return
        
        visited.add(room)
        
        # Visit all rooms we can unlock from here
        for key in rooms[room]:
            dfs(key)
    
    # Start DFS from room 0
    dfs(0)
    
    # Check if we visited all rooms
    return len(visited) == n

Complexity

• Time Complexity: O(n + k) - Where n is the number of rooms and k is the total number of keys. We visit each room once and process each key once.
• Space Complexity: O(n) - For the visited set and BFS queue (or DFS recursion stack).

Approach

The solution uses BFS/DFS graph traversal:

1. Start from room 0: Room 0 is initially unlocked
2. BFS/DFS traversal:
   • Visit room 0
   • Collect all keys from room 0
   • Visit rooms that we have keys for
   • Repeat until no new rooms can be visited
3. Track visited: Use a set to track which rooms have been visited
4. Check completion: After traversal, check if visited.size === n

Key Insights

• Graph traversal: Rooms are nodes, keys are edges
• BFS/DFS: Both work, BFS is level-by-level, DFS is recursive
• Start from room 0: Only room 0 is initially unlocked
• Collect keys: Keys from visited rooms unlock new rooms
• Reachability: Problem is about finding if all rooms are reachable from room 0

Step-by-Step Example

Let's trace through Example 1: rooms = [[1], [2], []]

Initial: visited = {}, queue = [0]

Step 1: Process room 0
  visited = {0}
  Keys in room 0: [1]
  Room 1 not visited → add to queue
  queue = [1]

Step 2: Process room 1
  visited = {0, 1}
  Keys in room 1: [2]
  Room 2 not visited → add to queue
  queue = [2]

Step 3: Process room 2
  visited = {0, 1, 2}
  Keys in room 2: [] (no keys)
  queue = []

Step 4: Check completion
  visited.size = 3
  n = 3
  3 === 3 → true

Result: true (all rooms visited)

Let's trace through Example 2: rooms = [[1, 2], [2], [0], []]

Initial: visited = {}, queue = [0]

Step 1: Process room 0
  visited = {0}
  Keys in room 0: [1, 2]
  Rooms 1 and 2 not visited → add to queue
  queue = [1, 2]

Step 2: Process room 1
  visited = {0, 1}
  Keys in room 1: [2]
  Room 2 already in queue → skip
  queue = [2]

Step 3: Process room 2
  visited = {0, 1, 2}
  Keys in room 2: [0]
  Room 0 already visited → skip
  queue = []

Step 4: Check completion
  visited.size = 3
  n = 4
  3 !== 4 → false

Result: false (room 3 not visited)

Visual Representation

Example 1: rooms = [[1], [2], []]
Graph:
  0 → 1 → 2
  ✓   ✓   ✓
All rooms reachable → true

Example 2: rooms = [[1, 2], [2], [0], []]
Graph:
  0 → 1 → 2
  ↓   ↓   ↑
  └───┴───┘
  
  3 (isolated)
  ✗
Room 3 not reachable → false

Edge Cases

• Single room: Return true (room 0 is always accessible)
• Room 0 has no keys: Return true if n = 1, false if n > 1
• All rooms reachable: Return true
• Some rooms isolated: Return false
• Circular dependencies: Works correctly (visited set prevents infinite loops)

Important Notes

• Room 0 unlocked: Always start from room 0
• Keys are room numbers: Each key is the number of a room to unlock
• No duplicates: Each room number appears at most once in keys
• Graph problem: This is essentially checking if all nodes are reachable from node 0
• BFS/DFS equivalent: Both give the same result

Related Problems

• Number of Islands: Different graph traversal problem
• Course Schedule: Check if all courses can be taken
• Clone Graph: Graph traversal with cloning
• Word Ladder: BFS pathfinding

Takeaways

• Graph traversal (BFS/DFS) solves reachability problems
• Start from room 0 is the key constraint
• Collect keys as we visit rooms
• Visited set prevents revisiting and infinite loops
• O(n + k) time is optimal (must process all rooms and keys)