Why it works
- 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.
- 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.
- 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 ↗