There are n rooms labeled 0 to n-1. All rooms are locked except room 0. Each room contains a set of keys to other rooms. Given rooms[i] – the set of keys in room i – return true if you can visit all rooms.

Examples

Example 1:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: Room 0 → key 1 → Room 1 → key 2 → Room 2 → key 3 → Room 3

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: Room 2 is never reachable.

Constraints

  • n == rooms.length
  • 2 <= n <= 1000
  • 0 <= rooms[i].length <= 1000
  • 1 <= sum(rooms[i].length) <= 3000
  • 0 <= rooms[i][j] < n
  • All values of rooms[i] are unique

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Graph Abstraction

Each room is a node and each key is a directed edge to another room. Starting from room 0, can we reach all nodes?

This is a graph reachability problem – standard DFS or BFS from a starting node.

Algorithm

  1. Start from room 0
  2. Traverse reachable rooms using DFS or BFS
  3. Track visited rooms
  4. If visited.size() == n, all rooms are reachable
Graph BFS layers S a b t BFS: expand by layers (queue)

Approach 1: DFS (Stack) – O(V + E)

Input: rooms = [[1],[2],[3],[]]
Output: True
# Start in 0, get key for 1.
# From 1, get key for 2.
# From 2, get key for 3.
# All rooms are reachable.

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: ### Graph Abstraction

How the code works:

  1. Start from room 0
  2. Traverse reachable rooms using DFS or BFS
  3. Track visited rooms
  4. If visited.size() == n, all rooms are reachable

Walkthrough — input rooms = [[1],[2],[3],[]], expected output true:

Room 0 → key 1 → Room 1 → key 2 → Room 2 → key 3 → Room 3

Approach 2: BFS (Queue) – O(V + E)

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: False
# Room 2 is never reachable; we never get key 2.

Time: O(V + E) Space: O(V)

Common Mistakes

  • Starting with all rooms as “visitable” instead of just room 0
  • Not marking rooms as visited when adding to the stack/queue (causes duplicates)
  • Treating this as an undirected graph (keys are one-way: having key to room 3 doesn’t mean room 3 has a key back)

Key Takeaways

  • “Can we reach all nodes from a source?” = graph reachability = DFS or BFS
  • The rooms/keys metaphor maps directly to an adjacency list: rooms[i] is the neighbor list for node i
  • Both DFS and BFS give the same result here since we only care about reachability, not shortest path

References

Template Reference