Keys and Rooms

Medium#841graph

There are n locked rooms numbered from 0, and only room 0 is open. Each room has some keys lying in it, each opening one room. Find out whether you can get into every room. Our example: the keys in rooms 0 to 4 are [1, 3], [3, 0], [4], [], [2] — the answer is false.

841 Keys and RoomsWalkthrough · 1×

Example: find out whether every room opens when the rooms hold the keys [1, 3], [3, 0], [4], [], [2].

0keys1, 31keys3, 02keys43keys—4keys2queuefront on the left—
locked, no key yetkey found, in the queueroom being searchedsearchednever opened

Room 0 is open from the start: visited = {0}

01/22
restart · back · play · step
Speed
1function canVisitAllRooms(rooms):
2 visited = {0}
3 queue = [0]
4 while queue is not empty:
5 room = queue.popFront()
6 for key in rooms[room]:
7 if key not in visited:
8 visited.add(key)
9 queue.pushBack(key)
10 return visited.size == rooms.size
state
visited
{0}
queue
–
room
–
key
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A key is an edge from the room it lies in to the room it opens, so the rooms you can get into are exactly the ones reachable from room 0.
  2. A room is marked as soon as its key is found, so each room is queued and searched once, however many keys to it there are.
  3. When the queue runs dry, every key in every opened room has been tried; any room still unmarked has no key in reach.

Complexity

Time O(n + k), where k is the number of keys: each room is searched once and each key is looked at once. Memory O(n) for visited and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.