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
Trueif all rooms visited, elseFalse. - 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
- Initialize a boolean array or set
visitedto track entered rooms, marking room0as visited immediately since it’s unlocked by default. - Use a stack (for DFS) or queue (for BFS). Push room
0. - 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.
- After traversal finishes (stack empty), check if all rooms are marked
visited.
Complexity Analysis
- Time Complexity: , where is the number of rooms (
len(rooms)) and is the total number of keys across all lists. Each room is pushed onto the stack at most once (), and each key is inspected exactly once during neighbor processing (). The final checksum(visited)takes , keeping overall complexity linear relative to input size representation. - Space Complexity: . We store a visited array of size and the stack/queue can hold at most 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 room0, stack empties.sum(visited)is 1, which equalsn. ReturnsTrue. 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
0has an empty list and , stack empties immediately. Visited count is 1, which does not equaln. ReturnsFalse. Correctly identifies unreachable rooms. - Cycles/Backtracking: The
visitedcheck 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.