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 Sam K., 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

More Graphs practice problems

See all Graphs problems →