LeetCode 841 - Keys and Rooms

This problem can be interpreted as a graph traversal challenge. Each room is a node in a graph labeled from 0 to n-1, and the keys inside a room represent directed edges to other nodes that can be unlocked.

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theory

LeetCode Problem 841

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

This problem can be interpreted as a graph traversal challenge. Each room is a node in a graph labeled from 0 to n-1, and the keys inside a room represent directed edges to other nodes that can be unlocked. The input rooms is a list of lists, where rooms[i] contains the set of keys found in room i. Each key in rooms[i] allows access to another room, potentially unlocking additional keys.

The goal is to determine whether it is possible to visit all rooms starting from room 0. The output is a boolean: true if all rooms can be visited, false otherwise. The constraints indicate that the number of rooms n can go up to 1000, and the total number of keys across all rooms is at most 3000. This ensures that the graph is sparse relative to a fully connected graph, and allows for linear traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS) to perform efficiently.

Important edge cases include rooms with no keys, cycles in key access (e.g., room A has key to B and B has key to A), and rooms whose keys do not lead to any unvisited room. The problem guarantees all keys in a room are unique and within bounds, so we do not need to handle invalid keys.

Approaches

A brute-force approach would attempt to generate all possible sequences of visiting rooms and check if any sequence allows visiting all rooms. This is correct but computationally infeasible, as the number of sequences grows factorially with n.

The key insight for an optimal solution is that we do not need to consider all sequences; we only need to traverse the graph of rooms using either DFS or BFS. Once a room is visited, we mark it as visited to avoid redundant traversal. Using either DFS or BFS ensures that all reachable rooms from room 0 are explored efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all sequences of room visits; infeasible for large n
Optimal (DFS/BFS) O(n + k) O(n) Traverse graph, n rooms and k total keys

Here, k is the total number of keys across all rooms.

Algorithm Walkthrough

  1. Initialize a set or boolean array visited to keep track of rooms that have been visited.
  2. Initialize a stack (for DFS) or queue (for BFS) and start with room 0.
  3. While the stack or queue is not empty, pop a room to visit.
  4. If the room has already been visited, skip it.
  5. Mark the room as visited.
  6. For each key found in the current room, push or enqueue the corresponding room to the stack or queue.
  7. Continue until all reachable rooms have been processed.
  8. At the end, check if the number of visited rooms equals n. Return true if all rooms have been visited, false otherwise.

Why it works: The traversal explores every room reachable from room 0. If any room is unreachable, it will not be added to the visited set, and the final check ensures correctness. This approach guarantees linear-time exploration relative to the size of the input.

Python Solution

from typing import List

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False] * len(rooms)
        stack = [0]

        while stack:
            room = stack.pop()
            if not visited[room]:
                visited[room] = True
                for key in rooms[room]:
                    if not visited[key]:
                        stack.append(key)
        
        return all(visited)

In this Python implementation, visited is a boolean array indicating which rooms have been visited. A stack is used for DFS. We iterate until the stack is empty, visiting rooms and adding new rooms found through keys. Finally, all(visited) ensures every room has been visited.

Go Solution

func canVisitAllRooms(rooms [][]int) bool {
    n := len(rooms)
    visited := make([]bool, n)
    stack := []int{0}

    for len(stack) > 0 {
        room := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if !visited[room] {
            visited[room] = true
            for _, key := range rooms[room] {
                if !visited[key] {
                    stack = append(stack, key)
                }
            }
        }
    }

    for _, v := range visited {
        if !v {
            return false
        }
    }
    return true
}

In Go, slices are used for both the stack and the visited array. The logic mirrors the Python DFS, with explicit slice operations for pushing and popping elements. The final check iterates through visited to confirm all rooms are accessible.

Worked Examples

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

Step Stack Visited Action
1 [0] [F,F,F,F] Pop 0, mark visited, push keys [1]
2 [1] [T,F,F,F] Pop 1, mark visited, push keys [2]
3 [2] [T,T,F,F] Pop 2, mark visited, push keys [3]
4 [3] [T,T,T,F] Pop 3, mark visited, push no keys
5 [] [T,T,T,T] Stack empty, all visited → return True

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

Step Stack Visited Action
1 [0] [F,F,F,F] Pop 0, mark visited, push keys [1,3]
2 [1,3] [T,F,F,F] Pop 3, mark visited, push keys [0] (already visited)
3 [1] [T,F,F,T] Pop 1, mark visited, push keys [3,0,1] (already visited)
4 [] [T,T,F,T] Stack empty, room 2 not visited → return False

Complexity Analysis

Measure Complexity Explanation
Time O(n + k) We visit each room at most once and process each key once; k is total keys
Space O(n) Stack/queue and visited array both scale with number of rooms

This ensures the algorithm is efficient even for the maximum constraints (n = 1000, sum(rooms[i].length) = 3000).

Test Cases

# Provided examples
assert Solution().canVisitAllRooms([[1],[2],[3],[]]) == True  # can visit all rooms
assert Solution().canVisitAllRooms([[1,3],[3,0,1],[2],[0]]) == False  # cannot visit room 2

# Boundary cases
assert Solution().canVisitAllRooms([[1],[]]) == True  # smallest n=2
assert Solution().canVisitAllRooms([[1,2],[2],[3],[]]) == True  # sequential keys

# Complex cycles
assert Solution().canVisitAllRooms([[1,2],[2,0],[3],[0]]) == True  # cycles in keys
assert Solution().canVisitAllRooms([[1],[2],[0],[]]) == True  # cycle, but all reachable

# Room with no keys
assert Solution().canVisitAllRooms([[1],[],[3],[]]) == False  # room 2 unreachable
Test Why
[[1],[2],[3],[]] Standard sequential unlock
[[1,3],[3,0,1],[2],[0]] Room unreachable
[[1],[]] Minimal size case
[[1,2],[2],[3],[]] Sequential access with multiple keys
[[1,2],[2,0],[3],[0]] Graph with cycles
[[1],[2],[0],[]] All reachable despite cycles
[[1],[],[3],[]] Some rooms blocked due to missing keys

Edge Cases

  1. Rooms with no keys: If a room has no keys, it cannot unlock any further rooms. The implementation correctly handles this because only unvisited rooms with keys are pushed onto the stack.
  2. Cycles in key access: Rooms may form cycles. For example, room 2 may contain a key to room 0, which has already been visited. The visited array ensures that we do not revisit rooms and avoids infinite loops.
  3. Disconnected rooms: Some rooms may not be reachable from room 0 if no keys lead to them. The algorithm detects this in the final all(visited) check, returning false if any room remains unvisited. This guarantees correctness even in sparse graphs.

This solution is robust, efficient, and handles all the constraints and edge cases specified by the problem.