Problem Description

You are given n rooms numbered from 0 to n - 1. Initially, all rooms are locked except room 0, which you can enter freely.

Each room contains a set of keys. When you visit a room, you collect all the keys in that room. Each key is labeled with a number indicating which room it can unlock. For example, if you find a key labeled 3 in a room, you can use it to unlock and enter room 3.

The input rooms is an array where rooms[i] represents the list of keys you can find in room i. Your task is to determine whether it's possible to visit all n rooms starting from room 0.

How the solution works:

The solution uses Depth-First Search (DFS) to explore all reachable rooms:

1. Start from room 0 (the only unlocked room initially)
2. When visiting a room, mark it as visited using a set vis
3. Collect all keys in the current room and recursively visit each room that these keys unlock
4. If a room has already been visited, skip it to avoid infinite loops
5. After the DFS completes, check if the number of visited rooms equals the total number of rooms

The function returns True if all rooms can be visited (i.e., len(vis) == len(rooms)), and False otherwise.

Example walkthrough:

If rooms = [[1], [2], [3], []]:

• Start in room 0, find key 1
• Visit room 1, find key 2
• Visit room 2, find key 3
• Visit room 3, find no keys
• All 4 rooms visited → return True

If rooms = [[1, 3], [3, 0, 1], [2], [0]]:

• Start in room 0, find keys 1 and 3
• Visit room 1, find keys 3, 0, 1 (already have these)
• Visit room 3, find key 0 (already have)
• Cannot reach room 2 → return False

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves rooms (nodes) and keys that unlock other rooms (edges). Room i has keys that point to other rooms, forming a directed graph structure.

Is it a tree?

• No: The graph can have cycles (a room can have a key back to a previously visited room) and multiple paths to the same room. It's not necessarily hierarchical like a tree.

Is the problem related to directed acyclic graphs?

• No: The graph can contain cycles. For example, room 1 might have a key to room 2, and room 2 might have a key back to room 1.

Is the problem related to shortest paths?

• No: We don't need to find the shortest path to any room. We only need to determine if all rooms are reachable from room 0.

Does the problem involve connectivity?

• Yes: The core question is about connectivity - can we reach all rooms starting from room 0? We need to explore which rooms are connected (reachable) from the starting room.

Does the problem have small constraints?

• Yes: The constraints are typically small (n ≤ 3000 rooms), making DFS/backtracking feasible without worrying about stack overflow or time limits.

DFS/backtracking?

• Yes: DFS is perfect for exploring all reachable rooms from room 0. We recursively visit each room, collect its keys, and explore the rooms those keys unlock.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to explore the graph of rooms and determine if all rooms are reachable from the starting room 0.

Intuition

Think of this problem like exploring a building where you start in the lobby (room 0) and need to determine if you can visit every room. Each room contains keys to other rooms, and once you pick up a key, you can use it anytime.

The key insight is that this is a reachability problem in a directed graph. Each room is a node, and having a key to a room creates a directed edge to that room. Starting from room 0, we need to explore all rooms we can reach by following these edges.

Why DFS works perfectly here:

1. Natural exploration pattern: When you enter a room, you immediately want to explore all the rooms whose keys you just found. This matches DFS's behavior of going as deep as possible before backtracking.

2. No need to track paths: We don't care about the order or path we take to visit rooms - we only care about whether we can eventually reach all rooms. This makes DFS simpler than algorithms that track distances or paths.

3. Avoiding revisits: Once we've visited a room and collected its keys, there's no benefit to visiting it again. We use a visited set to mark rooms we've already explored, preventing infinite loops in case of cycles (like room A having a key to room B, and room B having a key back to room A).

The solution naturally emerges: Start a DFS from room 0, mark each visited room, and recursively explore all rooms whose keys we find. After the DFS completes, if the number of visited rooms equals the total number of rooms, we know all rooms are reachable. If some rooms remain unvisited, it means they're disconnected from room 0's reachable component - we can never get keys to those rooms no matter how we explore.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The implementation uses Depth-First Search (DFS) with a recursive approach and a set to track visited rooms.

Data Structures Used:

• vis: A set to store visited room numbers. Using a set gives us O(1) lookup time to check if a room has been visited.

Algorithm Steps:

1. Initialize the visited set: Create an empty set vis to track which rooms we've explored.

2. Define the DFS function:

   def dfs(i: int):
       if i in vis:
           return
       vis.add(i)
       for j in rooms[i]:
           dfs(j)

   • Takes a room number i as input
   • First checks if room i has already been visited - if yes, return immediately (base case)
   • Mark room i as visited by adding it to vis
   • Iterate through all keys found in rooms[i] and recursively visit each unlocked room

3. Start DFS from room 0: Call dfs(0) since room 0 is the only initially unlocked room.

4. Check if all rooms are visited: Compare len(vis) with len(rooms):

   • If equal: All rooms were reachable, return True
   • If less: Some rooms couldn't be reached, return False

Why this works:

• The DFS explores all rooms reachable from room 0 by following available keys
• The visited set prevents infinite loops and redundant exploration
• After DFS completes, vis contains exactly the set of reachable rooms
• If this set's size equals the total number of rooms, we've successfully visited all rooms

Time Complexity: O(N + K) where N is the number of rooms and K is the total number of keys across all rooms. We visit each room at most once and examine each key once.

Space Complexity: O(N) for the visited set and the recursion call stack in the worst case.

Example Walkthrough

Let's walk through a small example with rooms = [[1,2], [3], [], [2]] to illustrate the DFS solution approach.

Initial Setup:

• We have 4 rooms (0, 1, 2, 3)
• Room 0 contains keys [1, 2]
• Room 1 contains key [3]
• Room 2 contains no keys []
• Room 3 contains key [2]
• Only room 0 is initially unlocked
• vis = {} (empty set)

Step-by-step DFS execution:

Step 1: Call dfs(0)

• Check: Is 0 in vis? No, so continue
• Add 0 to vis: vis = {0}
• Room 0 has keys [1, 2], so we'll call dfs(1) and dfs(2)

Step 2: Call dfs(1) (first key from room 0)

• Check: Is 1 in vis? No, so continue
• Add 1 to vis: vis = {0, 1}
• Room 1 has key [3], so call dfs(3)

Step 3: Call dfs(3) (key from room 1)

• Check: Is 3 in vis? No, so continue
• Add 3 to vis: vis = {0, 1, 3}
• Room 3 has key [2], so call dfs(2)

Step 4: Call dfs(2) (key from room 3)

• Check: Is 2 in vis? No, so continue
• Add 2 to vis: vis = {0, 1, 2, 3}
• Room 2 has no keys, so this branch ends
• Return to Step 3

Step 5: Back in Step 3, done with room 3

• Return to Step 2

Step 6: Back in Step 2, done with room 1

• Return to Step 1

Step 7: Back in Step 1, now call dfs(2) (second key from room 0)

• Check: Is 2 in vis? Yes (added in Step 4), so return immediately
• Back to Step 1

Step 8: DFS complete

• Check: len(vis) = 4, len(rooms) = 4
• Since 4 == 4, return True

All rooms were successfully visited! The DFS explored the path 0→1→3→2, and when it tried to revisit room 2 from room 0's second key, it correctly skipped it since it was already visited.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the number of rooms and m is the total number of keys across all rooms (edges in the graph). The DFS algorithm visits each room at most once due to the visited set check, contributing O(n). Additionally, we iterate through all keys in the rooms we visit, contributing O(m). Since we explore each edge (key) exactly once when we visit a room, the total time complexity is O(n + m).

The space complexity is O(n), where n is the number of rooms. This accounts for:

• The visited set vis which can store at most n room indices: O(n)
• The recursive call stack depth in the worst case (when rooms form a linear chain): O(n)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Empty Input or Edge Cases

A common mistake is not considering edge cases like when rooms is empty or contains only one room.

Pitfall Example:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = set()
    def dfs(i):
        vis.add(i)  # Might throw error if rooms is empty
        for j in rooms[i]:
            if j not in vis:
                dfs(j)
    dfs(0)  # Assumes room 0 exists
    return len(vis) == len(rooms)

Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    if not rooms:  # Handle empty input
        return True
  
    vis = set()
    def dfs(i):
        if i in vis:
            return
        vis.add(i)
        for j in rooms[i]:
            dfs(j)
  
    dfs(0)
    return len(vis) == len(rooms)

2. Forgetting to Check Visited Status Before Recursion

Without checking if a room is already visited before making the recursive call, the algorithm may enter infinite loops or have poor performance.

Pitfall Example:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = set()
    def dfs(i):
        vis.add(i)
        for j in rooms[i]:
            dfs(j)  # No check - will revisit rooms indefinitely
    dfs(0)
    return len(vis) == len(rooms)

Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = set()
    def dfs(i):
        if i in vis:  # Check before processing
            return
        vis.add(i)
        for j in rooms[i]:
            dfs(j)  # Now safe to recurse
    dfs(0)
    return len(vis) == len(rooms)

3. Using a List Instead of a Set for Tracking Visited Rooms

Using a list for vis leads to O(n) lookup time when checking if a room has been visited, significantly degrading performance.

Pitfall Example:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = []  # List has O(n) lookup time
    def dfs(i):
        if i in vis:  # This is O(n) operation
            return
        vis.append(i)
        for j in rooms[i]:
            dfs(j)
    dfs(0)
    return len(vis) == len(rooms)

Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = set()  # Set has O(1) lookup time
    def dfs(i):
        if i in vis:  # This is O(1) operation
            return
        vis.add(i)
        for j in rooms[i]:
            dfs(j)
    dfs(0)
    return len(vis) == len(rooms)

4. Stack Overflow with Deep Recursion

For inputs with many rooms in a linear chain, recursive DFS might cause stack overflow. Consider using iterative DFS for production code.

Pitfall Example:

# Recursive approach might fail with deep chains
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = set()
    def dfs(i):
        if i in vis:
            return
        vis.add(i)
        for j in rooms[i]:
            dfs(j)  # Deep recursion might overflow
    dfs(0)
    return len(vis) == len(rooms)

Solution (Iterative Approach):

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    vis = set([0])  # Start with room 0 visited
    stack = [0]  # Use explicit stack instead of recursion
  
    while stack:
        current_room = stack.pop()
        for key in rooms[current_room]:
            if key not in vis:
                vis.add(key)
                stack.append(key)
  
    return len(vis) == len(rooms)