Keys and Rooms

Determine if you can unlock every room using keys found along the way.

graph dfs bfs traversal

You are given `n` rooms labeled from `0` to `n - 1` and you initially start in room `0`. Each room `i` contains a list of keys `rooms[i]`; each key is an integer representing the room it can unlock. However, you can only enter a room if you have its key. Keys are not consumed when used, and you may collect all keys in a room upon entering. Write a function `can_visit_all_rooms(rooms)` that returns `True` if you can visit every room, or `False` otherwise. The input `rooms` is a list of lists, where `rooms[i]` is the list of keys in room `i`. All rooms are initially locked except room `0`, which is open.

Constraints

Number of rooms `n` satisfies `1 <= n <= 1000`. Each room's key list can contain duplicates. Each key is in the range `[0, n-1]`. The total number of keys across all rooms is at most `10^5`.

Example

print(can_visit_all_rooms([[1],[2],[3],[]]))  # True
print(can_visit_all_rooms([[1,3],[3,0,1],[2],[0]]))  # False
print(can_visit_all_rooms([[1],[],[3],[2]]))  # False

10 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Treat rooms as nodes and keys as directed edges from room i to room j.

Use a stack or queue to simulate the exploration from room 0.

Track visited rooms to avoid infinite loops.

At the end, check if the number of visited rooms equals the total number of rooms.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.