Skip to main content

841. Keys and Rooms

medium

Starting in room 0, each room hands you keys to other rooms. Determine if you can visit every room. A straightforward reachability problem disguised as a puzzle — DFS or BFS from node 0.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key. When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms. Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Constraints

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

Examples

Example 1

Input
rooms = [[1],[2],[3],[]]
Output
true

Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.

Example 2

Input
rooms = [[1,3],[3,0,1],[2],[0]]
Output
false

Explanation: We cannot enter room 2 since the only key that unlocks it is in that room.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Rooms are nodes, keys are directed edges. The question is: is every node reachable from node 0?

Hint 2

Run DFS or BFS from room 0, marking each visited room. At the end, check if the visited count equals n.

Hint 3

No need to model keys explicitly — picking up keys is the same as expanding the frontier to those neighbors in the graph traversal.

Solution approach

Reveal approach

Standard reachability from node 0. Use a visited set (or boolean array of size n), seed it with 0, and DFS: visit current room, then for each key in rooms[current] that isn't already visited, mark it and recurse. After traversal, return visited.size == n. BFS is identical with a queue. The 'keys' framing is just an adjacency list — room i lists the rooms you can enter from i, which is exactly outgoing edges in a directed graph. You don't carry state about which keys you hold because once visited, you can re-enter freely. O(n + sum(rooms[i].length)) = O(V + E) time, O(V) space.

Complexity

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

Related patterns

  • graph-dfs
  • graph-bfs

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Keys and Rooms and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →