Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Keys and Rooms (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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<sup>th</sup> 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:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible