Editor

Keys in Locked Rooms

#271 · Graphs · Intermediate · 60 XP · about 10 min

A museum has n rooms, numbered 0 to n - 1. At night every room is locked except room 0, where you start. keys[i] is the list of keys lying in room i, and a key with the number k unlocks room k. Once a room is unlocked you can walk into it whenever you like and pick up every key inside.

Write locked_rooms(keys) that returns a sorted list of the rooms you can never get into. If you can visit every room, return [].

Examples

locked_rooms([[1], [2], [3], []])  # returns []
locked_rooms([[1, 3], [3, 0, 1], [2], [0]])  # returns [2]
locked_rooms([[], [0]])  # returns [1]

In the second museum, room 0 gives you the keys to rooms 1 and 3, but the only key to room 2 lies inside room 2 itself.

Constraints

  • 1 <= n <= 500, with up to 5,000 keys in all.
  • Every key number is a room number from 0 to n - 1. A room can hold several copies of the same key, its own key, or the key to room 0.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.