Keys and Rooms — Editorial

Opening the reading…

Intuitiona key is a directed path to another room

Room 0 is the only place you can enter initially, so every successful visit must begin there. Once you enter a room, each key inside gives you a possible next room. That means a key from room u to room v behaves exactly like a directed graph edge from u to v.

The question is therefore whether every room is reachable from room 0. Start at room 0, follow every key you can obtain, and continue from each newly reached room. A visited array prevents cycles and repeated work: finding a key for a room you already reached cannot unlock anything new.

Approach

Let n be the number of rooms and create visited with one false entry per room, because the search must distinguish rooms reached from rooms that are still locked.

Mark room 0 visited and put it on a stack, because it is the only room available before any key has been collected.

While the stack is not empty, remove one room u, because every room taken from the stack is a room whose keys still need to be examined.

For each key v in rooms[u], check whether v is unvisited, because an already visited room adds no new reachable rooms and pushing it again can repeat work around a cycle.

When v is new, mark it visited before pushing it, because marking on discovery prevents the same room from being inserted several times through different keys.

Push every newly visited room onto the stack, because its keys may unlock further rooms that are not reachable from the current room alone.

After the search ends, return whether the number of visited rooms equals n, because an empty stack means no further key path exists and any unvisited room is permanently unreachable.

Complexitycounting rooms and key entries separately

MEASURE	BOUND	WHY
Time	O(n + m)	Each reachable room is removed from the stack once, and the keys in that room are scanned once. A key entry is therefore inspected at most once, while the room bookkeeping contributes O(n).
Space	O(n)	The visited array uses O(n) space and the stack holds at most n room numbers. The boolean result is not stored as output, and there is no separate output structure; in the worst shape, all rooms can be reachable and occupy the stack or visited array.

Here n is the number of rooms and m is the total number of keys across all rooms.

Annotated solutionC++ · iterative DFS with a discovery count

CPPIterative depth-first search from room 0, returning whether every room was discovered.

#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = static_cast<int>(rooms.size());
        vector<bool> visited(n, false);
        stack<int> st;

        st.push(0);
        visited[0] = true;
        int seen = 1;

        while (!st.empty()) {
            int u = st.top();
            st.pop();

            for (int v : rooms[u]) {
                if (v >= 0 && v < n && !visited[v]) {
                    visited[v] = true;
                    seen++;
                    st.push(v);
                }
            }
        }

        return seen == n;
    }
};

The important placement is visited[v] = true before st.push(v). Two different rooms may contain keys to the same destination, and a cycle may lead back to an earlier room. Marking at discovery means the first key claims that room immediately, so later keys cannot add duplicate stack entries.

The seen counter is not required; you could scan visited after the search. It makes the final test direct: every successful discovery increases seen once, so seen == n means every room belongs to the reachable region. The bounds check is defensive because the stated input keeps every key between 0 and n - 1.

The recursive alternativethe same DFS with the stack kept by the runtime

CPPRecursive depth-first search with the call stack representing pending rooms.

#include <vector>

using namespace std;

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = static_cast<int>(rooms.size());
        vector<bool> visited(n, false);
        int seen = 0;

        dfs(0, rooms, visited, seen);
        return seen == n;
    }

private:
    void dfs(int u, const vector<vector<int>>& rooms,
             vector<bool>& visited, int& seen) {
        visited[u] = true;
        seen++;

        for (int v : rooms[u]) {
            if (!visited[v]) {
                dfs(v, rooms, visited, seen);
            }
        }
    }
};

This is a different arrangement, not an asymptotic optimisation. The recursive call stack replaces the explicit stack, so both versions use O(n) extra space in the worst case and inspect O(n + m) data. The iterative form gives you explicit control over pending rooms and avoids depending on the runtime call stack when a long chain of rooms is possible.