Keys and Rooms
The key idea
Treat each room as a graph node and each key as a directed edge to the room it unlocks. Starting from room 0, run a graph search and count how many distinct rooms you can reach. You can visit every room exactly when that reachable count equals the total number of rooms.
Problem
There are n rooms labeled from 0 to n - 1, and all the rooms are locked except for room 0. Your goal is to visit all the rooms, but you cannot enter a locked room without holding its key. When you visit a room you may find a set of distinct keys in it; each key is numbered with the room it unlocks, and you may carry every key you find to open other rooms. Given an array rooms where rooms[i] is the set of keys found in room i, return true if you can visit all the rooms, or false otherwise.
Constraints
- n == rooms.length
- 2 <= n <= 1000
- 0 <= rooms[i].length <= 1000
- 1 <= sum(rooms[i].length) <= 3000
- 0 <= rooms[i][j] < n
- All the values of rooms[i] are unique.
Examples
Input: rooms = [[1],[2],[3],[]]
Output: true
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Complexity
Time: O(n + e) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY