841 · Keys and Rooms — visual guide

There are n rooms labeled 0 to n - 1. All rooms start locked except room 0. Each room holds a set of distinct keys to other rooms. Return true if you can enter every room, or false otherwise.

Simulation & Graph View

idle

INVARIANT Directed Reachability Invariant: Keys represent directed edges (u → v). Room 0 is unlocked at start. A room is unlocked if and only if there is a directed path from 0. The goal is satisfied if and only if visited.count == n. Time is O(V + E), Space is O(V).

Unlocked:0 / 0

Current Room:-

Pocket Keys:[]

Press Run to begin.

0 / 0

Java 21 Solution

INTERVIEW SCRIPT

How to Explain Keys and Rooms to an Interviewer

1. Problem Framing

"This is reachability in a directed graph. Nodes are rooms 0..n-1, and keys inside room $u$ are directed edges $u \to v$."

2. Directed vs Undirected Trap

"Do not confuse this with undirected connected components! Having key 2 in room 1 lets us enter room 2, but does not allow returning to room 1 unless room 2 has key 1."

3. Traversal Mechanics

"We run a standard DFS or BFS seeded at room 0. Maintain a boolean visited[n] array and a counter unlockedCount. Whenever we unlock a room, iterate through its keys and push unvisited rooms."

4. Complexity Mastery

"Time complexity is $O(V + E)$ where $V = n$ and $E$ is total keys across all rooms. Space complexity is $O(V)$ for the visited array and recursion/queue stack."