Keys and Rooms
Medium · Graphs · Depth-First Search · Breadth-First Search · Graph
Problem
There are n rooms labeled 0 to n - 1. Room 0 is unlocked and every other room is locked. Inside room i you find the set of keys rooms[i]; a key with number j unlocks room j, and you can use keys you have collected at any time.
Return true if you can eventually enter every room, and false otherwise.
Examples
Input: rooms = [[2],[],[1,3],[]] Output: true
Room 0 gives key 2, and room 2 gives keys 1 and 3.
Input: rooms = [[1],[0],[3],[2]] Output: false
Rooms 2 and 3 only hold keys to each other, and you never reach either.
Input: rooms = [[1],[2],[3],[]] Output: true
Each room holds the key to the next one, so you walk through all four.
Constraints
- n == len(rooms)
- 2 <= n <= 1000
- 0 <= len(rooms[i]) <= 1000
- The total number of keys is at most 3000
- 0 <= rooms[i][j] < n
- All values inside one rooms[i] are unique
Approaches
- Sweep all opened rooms until nothing changes — time O(n · (n + K)), space O(n)
Follow-up
What if each room also needs a minimum number of keys collected before it opens, or keys are used up when they open a door? The order of opening then matters and plain reachability no longer answers it; the first becomes a search ordered by the requirement, the second a resource problem.
Related problems
Start free on Cariara · Coding problems · System design studio
