easy

Keys and Rooms

Use a stack to open rooms with the keys you collect, and decide whether every room can be reached from room 0.

1. Define the problem

Keys and Rooms

There are n rooms numbered 0 to n - 1. Every room is locked except room 0, and each room holds a list of keys that open other rooms. Starting in room 0, return true if you can visit every room , and false otherwise. Keep a stack of rooms you have opened but not yet searched. Take one off the stack, pick up its keys, open any room those keys unlock for the first time, and push those rooms on. When the stack runs dry, count how many rooms you opened.

Constraints

  • n === rooms.length, 2 ≤ n ≤ 1000
  • 0 ≤ roomsi.length ≤ 1000
  • Every key is a valid room number
  • A room may hold a key to itself or a duplicate key

Example

Inputrooms = [[1], [2], [3], []]
Outputtrue

Explanation Room 0 holds the key to room 1, room 1 holds the key to room 2, and room 2 holds the key to room 3. All four rooms get opened.

2. Know the words first

In plain terms

Stack
A pile where you always take the item you put down most recently. Pushing adds to the top, popping removes from the top.
Depth-first search
A way of exploring a graph where you follow one path as far as it goes before backing up and trying another. A stack gives you this for free.
Visited
A record of which rooms you have already opened, so you never open the same room twice and never loop forever.
Reachable
A room you can get to by following keys from room 0. Rooms that are not reachable are the reason the answer can be false.
3. Visualize the solution

One cell per room, value = open or shut

One cell per room, value = open or shut
Statusinit

You start inside room 0, so it is open and the other three are still shut.

What happens in this step

rooms = [[1], [2], [3], []]
stack = [0]
opened = 1

Room 0 is marked open straight away.
Rooms 1, 2 and 3 are shut until a key turns up.
Step 1 of 6

Steps to visualize

  1. The row has one cell per room. The label is the room number and the value says whether it is open yet.
  2. Room 0 starts open because you begin inside it. Everything else starts shut.
  3. Take a room off the stack and read the keys lying in it.
  4. Any key that opens a still-shut room flips that room to open and pushes it on the stack.
  5. When the stack is empty, compare the number of open rooms with the total number of rooms.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per room, value = open or shut
Statusinit

You start inside room 0, so it is open and the other three are still shut.

What happens in this step

rooms = [[1], [2], [3], []]
stack = [0]
opened = 1

Room 0 is marked open straight away.
Rooms 1, 2 and 3 are shut until a key turns up.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function canVisitAllRooms(rooms) {
  const visited = new Array(rooms.length).fill(false);
  const stack = [0];
  visited[0] = true;
  let opened = 1;

  while (stack.length > 0) {
    const room = stack.pop();

    for (const key of rooms[room]) {
      if (!visited[key]) {
        visited[key] = true;
        opened += 1;
        stack.push(key);
      }
    }
  }

  return opened === rooms.length;
}
Time
O(n + k), where k is the total number of keys
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
rooms = [[1], [2], [3], []]trueexample from the docstring
rooms = [[1, 3], [3, 0, 1], [2], [0]]falseone room holds the only key to itself and stays locked
rooms = [[1], []]truesmallest input, two rooms joined by one key
rooms = [[2], [], [1]]truerooms are opened in an order that skips ahead and comes back
rooms = [[1], [], [3], []]falsea separate pair of rooms nothing points at
rooms = [[0, 1, 1], [0, 2], [0]]truerepeated keys and keys to already open rooms

Keep reading