841. Keys and Rooms
Keys and Rooms (LeetCode 841) 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.
How to solve Keys and Rooms
Keys and Rooms is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.
Work towards the solution in these steps:
- Think of each room as a node in a graph, and keys inside a room as edges to other nodes you can visit.
- Use a graph traversal technique such as Depth-First Search (DFS) or Breadth-First Search (BFS) to explore reachable rooms starting from room 0.
- Maintain a visited set or array to keep track of rooms you have already unlocked and visited to avoid redundant searches.
The reference solution runs in O(N + E) time and O(N + E) space.
The Keys and Rooms solution and editorial walks through the full approach with reference code.
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) time and O(N + 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
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph DFS - Connected Components / Island Counting subpattern
- The full DSA patterns 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:
- Count Sub Islands — Medium, same subpattern
- Detonate the Maximum Bombs — Medium, same subpattern
- Evaluate Division — Medium, same subpattern
- Flood Fill — Easy, same subpattern
- Island Perimeter — Easy, same subpattern
- Max Area of Island — Medium, same subpattern
Keys and Rooms FAQ
What is the LeetCode number of Keys and Rooms?
Keys and Rooms is LeetCode problem 841, rated Medium.
What pattern is used to solve Keys and Rooms?
Keys and Rooms is a DFS Connected Components problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.
What is the time complexity of Keys and Rooms?
The reference solution runs in O(N + E) time and O(N + E) space.
Which companies ask Keys and Rooms?
Keys and Rooms has been reported in interviews at Amazon, Twitch.