Problem Statement

You are given n rooms labeled from 0 to n-1. Initially, you can only enter inside the room 0, and all other rooms are locked. However, you cannot enter a locked room without having its key.

Each room may contain a set of keys, each key opens a specific room. Each key has a number n on it, which opens up n^th room starting from 0, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms. Otherwise, return false.

Examples

Example 1:

• Input: rooms = [[1, 2], [1], [4, 3], [4], [3]]
• Expected Output: true
• Justification:
  • Visit room 0 and get keys to rooms 1 and 2.
  • Visit room 2 and get keys to rooms 3 and 4.

Example 2:

• Input: rooms = [[1,2,3], [], [], []]
• Expected Output: true
• Justification: All keys are in room 0, so you can unlock all rooms immediately.

Example 3:

• Input: rooms = [[3], [1], [2], [0]]
• Expected Output: false
• Justification: You can't visit rooms 1 and 2, as the keys for those rooms are in themselves.

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.

Try it yourself

Try solving this question here: