Keys and Rooms

Keys and Rooms is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

Problem statement

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. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, 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, or false otherwise.

Example 1:

Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

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.

Topics and companies

Topics: Depth-First Search, Breadth-First Search, Graph.

Reported in interviews at Amazon, Twitch.

How to practise Keys and Rooms on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N + E), where N is the number of rooms and E is the total number of keys (edges). Each room and key is visited at most once. time and O(N + E), for the visited array (O(N)), the stack (up to O(N)), and the input rooms (O(E)). space.

Open Keys and Rooms in the code editor, or read the Keys and Rooms editorial for a worked solution with its approach and complexity analysis.

Where Keys and Rooms sits in the DSA pattern sheet

Problems related to Keys and Rooms

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.