Keys and Rooms
Problem Statement
There are n rooms numbered 0 to n − 1. Room 0 starts unlocked, and every other room starts locked. Room i holds a list of keys, and a key with number k opens room k.
You start in room 0. Every time you enter a room, you can take all the keys in it, and you may enter any room whose key you already hold. Return true if you can enter every room, and false otherwise.
A list rooms of length n. rooms[i] is the list of keys found inside room i.
true if every room can be entered, otherwise false.
Room 0 holds key 1, room 1 holds key 2, and room 2 holds key 3. Walking 0 → 1 → 2 → 3 opens everything.
Key 2 is only found inside room 2, and you need key 2 to enter room 2. Nobody can get in, so the answer is false.
- • n = rooms.length
- • 2 ≤ n ≤ 1000
- • 0 ≤ rooms[i].length ≤ 1000
- • 1 ≤ sum of rooms[i].length ≤ 3000
- • 0 ≤ rooms[i][j] < n
- • All values in rooms[i] are unique.
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Each pass collects the keys in open rooms, then opens every room whose key is held; stop when a pass opens nothing
Enter rooms with a stack, mark each room the first time it is entered, then compare the count with n
Keep two arrays: open[i] (I have been inside room i) and haveKey[k] (I hold key k). Each pass first picks up the keys in every open room, then opens every closed room whose key is held. Passes repeat until a pass opens nothing new. The answer is true when every room is open.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.