517. Keys and Rooms
There are n rooms numbered 0 to n - 1. Every room except room 0 starts locked, and you cannot enter a locked room without its key.
Inside each room lies a pile of keys: your function receives rooms, where rooms[i] is the list of room numbers whose keys sit in room i (possibly empty, possibly with duplicates or a key to a room you already opened). Whenever you enter a room you may take all of its keys and keep them forever.
Starting in room 0, return true if you can eventually walk into every room, and false otherwise.
Example 1:
Input: rooms = [[1], [2], [3], []]
Output: true
Explanation: Room 0 yields the key to room 1, room 1 the key to room 2, and room 2 the key to room 3. Every room gets opened in a chain.
Example 2:
Input: rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: false
Explanation: From room 0 you can reach rooms 1 and 3, but the only key to room 2 is locked inside room 2 itself — it can never be entered.
Constraints:
- 1 ≤ rooms.length ≤ 1000
- 0 ≤ rooms[i].length ≤ 1000
- 0 ≤ rooms[i][j] < rooms.length
- The total number of keys across all rooms is at most 3000
Hints:
Rephrase as a graph: rooms are nodes and every key in room i is a directed edge i → key. The question becomes: is every node reachable from node 0?
Any traversal answers reachability. Recurse (DFS): visit a room, mark it, then recurse into every key you haven't used yet. At the end compare the count of visited rooms with n.
Keys to rooms you already visited are the cycle trap — without a visited set, rooms = [[1],[0]] recurses forever. Mark before you branch.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: rooms = [[1], [2], [3], []]
Expected output: true