Keys and Rooms

🎯

Keys and Rooms

mediumGRAPHAmazonGoogleFacebook

Imagine you are in a building with several locked rooms. Each room contains keys to other rooms. Can you visit every room starting from room 0?

💡 This problem is about exploring a graph where nodes represent rooms and edges represent keys to other rooms. Beginners often struggle because the problem is framed as keys and rooms, but it is essentially about graph traversal and reachability.

📋

Problem Statement

You are given an array rooms where rooms[i] is a list of keys in room i. Each key rooms[i][j] is an integer representing a room number you can unlock. Initially, you start in room 0. Return true if you can visit all the rooms, otherwise return false.

1 ≤ n ≤ 10^50 ≤ rooms[i][j] < nAll keys are unique within a roomThe graph may be disconnected except for room 0

💡

Example

Input"[[1],[2],[3],[]]"

Outputtrue

Start in room 0, get key 1, go to room 1, get key 2, go to room 2, get key 3, go to room 3. All rooms visited.

Input"[[1,3],[3,0,1],[2],[0]]"

Outputfalse

Room 2 is not reachable from room 0 because keys do not lead there.

• Only one room with no keys → true
• Rooms with no keys leading anywhere → false if not all visited
• Rooms with keys pointing back to already visited rooms → should not cause infinite loops
• Large number of rooms with linear chain of keys → true

⚠️

Common Mistakes

Not tracking visited rooms

Infinite recursion or repeated visits causing TLE

✅ Use a visited set or array to mark rooms visited

Using recursion without early stopping

Unnecessary exploration leading to slower runtime

✅ Add early exit once all rooms are visited

Confusing keys with rooms indices

Index errors or wrong room visits

✅ Remember keys represent room indices, always validate

Using BFS but forgetting to mark visited before enqueueing

Multiple enqueues of same room, increasing runtime

✅ Mark visited when enqueueing, not when dequeuing

Assuming all rooms have keys

Incorrectly concluding all rooms are reachable

✅ Check visited count against total rooms

🧠

DFS with Visited Set

💡 This approach uses DFS with a visited set to track rooms already visited, preventing infinite loops and repeated work. It helps understand basic graph traversal.

Intuition

Start from room 0 and recursively visit rooms using keys found, marking rooms as visited to avoid revisiting.

Algorithm

1. Start DFS from room 0.
2. For each key in the current room, recursively visit the corresponding room if not visited.
3. Track visited rooms to avoid infinite loops and repeated visits.
4. After DFS completes, check if all rooms have been visited by counting unique visits.

💡 Tracking visited rooms prevents infinite recursion and repeated work, making the traversal efficient and correct.

</>

Code

def canVisitAllRooms(rooms):
    visited = set()
    def dfs(room):
        visited.add(room)
        for key in rooms[room]:
            if key not in visited:
                dfs(key)
    dfs(0)
    return len(visited) == len(rooms)

# Driver code
if __name__ == '__main__':
    rooms = [[1],[2],[3],[]]
    print(canVisitAllRooms(rooms))  # True

Line Notes

visited = set()Initialize a set to keep track of visited rooms to avoid infinite loops

def dfs(room):Define recursive DFS function to explore rooms

visited.add(room)Mark current room as visited to prevent revisiting

for key in rooms[room]:Iterate over all keys in the current room to visit connected rooms

if key not in visited:Only recurse into rooms not yet visited to avoid cycles

import java.util.*;
public class KeysAndRooms {
    public static boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> visited = new HashSet<>();
        dfs(0, rooms, visited);
        return visited.size() == rooms.size();
    }
    private static void dfs(int room, List<List<Integer>> rooms, Set<Integer> visited) {
        visited.add(room);
        for (int key : rooms.get(room)) {
            if (!visited.contains(key)) {
                dfs(key, rooms, visited);
            }
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> rooms = new ArrayList<>();
        rooms.add(Arrays.asList(1));
        rooms.add(Arrays.asList(2));
        rooms.add(Arrays.asList(3));
        rooms.add(Collections.emptyList());
        System.out.println(canVisitAllRooms(rooms)); // true
    }
}

Line Notes

Set<Integer> visited = new HashSet<>()Track visited rooms to avoid infinite recursion

dfs(0, rooms, visited)Start DFS from room 0

visited.add(room)Mark current room as visited

for (int key : rooms.get(room))Visit all rooms accessible from current room

if (!visited.contains(key))Only recurse into unvisited rooms to prevent cycles

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

void dfs(int room, const vector<vector<int>>& rooms, unordered_set<int>& visited) {
    visited.insert(room);
    for (int key : rooms[room]) {
        if (visited.find(key) == visited.end()) {
            dfs(key, rooms, visited);
        }
    }
}

bool canVisitAllRooms(const vector<vector<int>>& rooms) {
    unordered_set<int> visited;
    dfs(0, rooms, visited);
    return visited.size() == rooms.size();
}

int main() {
    vector<vector<int>> rooms = {{1}, {2}, {3}, {}};
    cout << (canVisitAllRooms(rooms) ? "true" : "false") << endl;
    return 0;
}

Line Notes

unordered_set<int> visited;Use a hash set to track visited rooms efficiently

void dfs(int room, const vector<vector<int>>& rooms, unordered_set<int>& visited)Recursive DFS function to explore rooms

visited.insert(room);Mark the current room as visited

for (int key : rooms[room])Iterate over keys to visit connected rooms

if (visited.find(key) == visited.end())Only recurse into unvisited rooms to avoid cycles

function canVisitAllRooms(rooms) {
    const visited = new Set();
    function dfs(room) {
        visited.add(room);
        for (const key of rooms[room]) {
            if (!visited.has(key)) {
                dfs(key);
            }
        }
    }
    dfs(0);
    return visited.size === rooms.length;
}

// Test
console.log(canVisitAllRooms([[1],[2],[3],[]])); // true

Line Notes

const visited = new Set();Track visited rooms to prevent infinite recursion

function dfs(room)Recursive DFS helper function

visited.add(room);Mark current room as visited

for (const key of rooms[room])Visit all rooms accessible from current room

if (!visited.has(key))Only recurse into unvisited rooms to avoid cycles

⏱

Complexity

TimeO(N + E)

SpaceO(N)

DFS visits each room and each key once, where N is number of rooms and E is total keys.

💡 For 100,000 rooms and keys, this means roughly 100,000 operations, which is feasible.

Interview Verdict: Accepted

This approach works well because it tracks visited rooms, preventing infinite loops and repeated work.

🧠

Iterative BFS

💡 Using BFS with a queue avoids recursion stack overflow and is easier to understand for some. It also tracks visited rooms to prevent revisiting.

Intuition

Start from room 0, add keys found to a queue, and iteratively visit rooms until no new rooms can be visited.

Algorithm

1. Initialize a queue with room 0 and a visited set.
2. While the queue is not empty, dequeue a room.
3. Add all keys from the current room to the queue if not visited.
4. After processing, check if all rooms have been visited.

💡 BFS explores rooms in layers, which can be easier to visualize and debug than recursion.

</>

Code

from collections import deque

def canVisitAllRooms(rooms):
    visited = set([0])
    queue = deque([0])
    while queue:
        room = queue.popleft()
        for key in rooms[room]:
            if key not in visited:
                visited.add(key)
                queue.append(key)
    return len(visited) == len(rooms)

# Driver code
if __name__ == '__main__':
    rooms = [[1],[2],[3],[]]
    print(canVisitAllRooms(rooms))  # True

Line Notes

visited = set([0])Start with room 0 marked visited

queue = deque([0])Initialize queue with starting room

room = queue.popleft()Process rooms in FIFO order for BFS

if key not in visitedAvoid revisiting rooms to prevent infinite loops

import java.util.*;
public class KeysAndRooms {
    public static boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(0);
        queue.offer(0);
        while (!queue.isEmpty()) {
            int room = queue.poll();
            for (int key : rooms.get(room)) {
                if (!visited.contains(key)) {
                    visited.add(key);
                    queue.offer(key);
                }
            }
        }
        return visited.size() == rooms.size();
    }
    public static void main(String[] args) {
        List<List<Integer>> rooms = new ArrayList<>();
        rooms.add(Arrays.asList(1));
        rooms.add(Arrays.asList(2));
        rooms.add(Arrays.asList(3));
        rooms.add(Collections.emptyList());
        System.out.println(canVisitAllRooms(rooms)); // true
    }
}

Line Notes

Set<Integer> visited = new HashSet<>()Track visited rooms

Queue<Integer> queue = new LinkedList<>()Use queue for BFS traversal

visited.add(0)Start from room 0

if (!visited.contains(key))Only enqueue unvisited rooms

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

bool canVisitAllRooms(const vector<vector<int>>& rooms) {
    unordered_set<int> visited;
    queue<int> q;
    visited.insert(0);
    q.push(0);
    while (!q.empty()) {
        int room = q.front();
        q.pop();
        for (int key : rooms[room]) {
            if (visited.find(key) == visited.end()) {
                visited.insert(key);
                q.push(key);
            }
        }
    }
    return visited.size() == rooms.size();
}

int main() {
    vector<vector<int>> rooms = {{1}, {2}, {3}, {}};
    cout << (canVisitAllRooms(rooms) ? "true" : "false") << endl;
    return 0;
}

Line Notes

unordered_set<int> visited;Keep track of visited rooms

queue<int> q;Queue for BFS traversal

visited.insert(0);Mark room 0 as visited initially

if (visited.find(key) == visited.end())Only add unvisited rooms to queue

function canVisitAllRooms(rooms) {
    const visited = new Set([0]);
    const queue = [0];
    while (queue.length > 0) {
        const room = queue.shift();
        for (const key of rooms[room]) {
            if (!visited.has(key)) {
                visited.add(key);
                queue.push(key);
            }
        }
    }
    return visited.size === rooms.length;
}

// Test
console.log(canVisitAllRooms([[1],[2],[3],[]])); // true

Line Notes

const visited = new Set([0]);Initialize visited with room 0

const queue = [0];Initialize queue with starting room

const room = queue.shift();Dequeue room for BFS processing

if (!visited.has(key))Prevent revisiting rooms

⏱

Complexity

TimeO(N + E)

SpaceO(N)

Each room and key is processed once in BFS, where N is rooms and E is keys.

💡 For 100,000 rooms, BFS will perform about 100,000 operations, which is efficient.

Interview Verdict: Accepted

BFS is a robust alternative to DFS, especially when recursion depth is a concern.

🧠

DFS with Early Exit and Visited Array

💡 This approach uses DFS with a boolean visited array for O(1) checks and stops early if all rooms are visited, improving efficiency.

Intuition

Use DFS to explore rooms, mark visited using an array for faster access, and stop recursion once all rooms are visited.

Algorithm

1. Initialize a boolean visited array and a counter for visited rooms.
2. Start DFS from room 0, mark visited and increment counter.
3. For each key, if not visited, recursively DFS.
4. If counter equals total rooms, stop recursion early.
5. Return true if all rooms visited, else false.

💡 Early stopping avoids exploring unnecessary paths once the goal is met, improving runtime.

</>

Code

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [False] * n
    count = 0
    def dfs(room):
        nonlocal count
        if visited[room]:
            return
        visited[room] = True
        count += 1
        if count == n:
            return
        for key in rooms[room]:
            dfs(key)
    dfs(0)
    return count == n

# Driver code
if __name__ == '__main__':
    rooms = [[1],[2],[3],[]]
    print(canVisitAllRooms(rooms))  # True

Line Notes

visited = [False] * nBoolean array for O(1) visited checks

count = 0Count how many rooms have been visited

if visited[room]: returnSkip already visited rooms to avoid cycles

if count == n: returnEarly exit when all rooms visited

import java.util.*;
public class KeysAndRooms {
    private static int count = 0;
    public static boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        count = 0;
        dfs(0, rooms, visited, n);
        return count == n;
    }
    private static void dfs(int room, List<List<Integer>> rooms, boolean[] visited, int n) {
        if (visited[room]) return;
        visited[room] = true;
        count++;
        if (count == n) return;
        for (int key : rooms.get(room)) {
            dfs(key, rooms, visited, n);
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> rooms = new ArrayList<>();
        rooms.add(Arrays.asList(1));
        rooms.add(Arrays.asList(2));
        rooms.add(Arrays.asList(3));
        rooms.add(Collections.emptyList());
        System.out.println(canVisitAllRooms(rooms)); // true
    }
}

Line Notes

boolean[] visited = new boolean[n];Use boolean array for fast visited checks

if (visited[room]) return;Avoid revisiting rooms

count++;Increment count when visiting a new room

if (count == n) return;Stop recursion early if all rooms visited

#include <iostream>
#include <vector>
using namespace std;

int count = 0;

void dfs(int room, const vector<vector<int>>& rooms, vector<bool>& visited, int n) {
    if (visited[room]) return;
    visited[room] = true;
    count++;
    if (count == n) return;
    for (int key : rooms[room]) {
        dfs(key, rooms, visited, n);
    }
}

bool canVisitAllRooms(const vector<vector<int>>& rooms) {
    int n = rooms.size();
    vector<bool> visited(n, false);
    count = 0;
    dfs(0, rooms, visited, n);
    return count == n;
}

int main() {
    vector<vector<int>> rooms = {{1}, {2}, {3}, {}};
    cout << (canVisitAllRooms(rooms) ? "true" : "false") << endl;
    return 0;
}

Line Notes

vector<bool> visited(n, false);Boolean vector for visited rooms

if (visited[room]) return;Skip rooms already visited

count++;Track number of visited rooms

if (count == n) return;Early exit to save time

let count = 0;
function canVisitAllRooms(rooms) {
    const n = rooms.length;
    const visited = new Array(n).fill(false);
    function dfs(room) {
        if (visited[room]) return;
        visited[room] = true;
        count++;
        if (count === n) return;
        for (const key of rooms[room]) {
            dfs(key);
        }
    }
    dfs(0);
    return count === n;
}

// Test
console.log(canVisitAllRooms([[1],[2],[3],[]])); // true

Line Notes

const visited = new Array(n).fill(false);Boolean array for visited rooms

if (visited[room]) return;Avoid revisiting rooms

count++;Count visited rooms

if (count === n) return;Stop recursion early if all rooms visited

⏱

Complexity

TimeO(N + E)

SpaceO(N)

Each room and key is visited once, early exit can improve average runtime.

💡 For large inputs, early stopping can save significant time by avoiding unnecessary exploration.

Interview Verdict: Accepted

This is the most optimized DFS approach, combining speed and safety against stack overflow.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimized DFS with early stopping is best for interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. DFS with Visited Set	O(N + E)	O(N)	Yes (deep recursion possible)	N/A	Good to introduce problem and basic traversal
2. Iterative BFS	O(N + E)	O(N)	No	N/A	Safe alternative to recursion, good for large inputs
3. DFS with Early Exit and Visited Array	O(N + E)	O(N)	Yes, but less work due to early exit	N/A	Optimal DFS approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly during interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force DFS approach and its limitations.Discuss BFS as an alternative to avoid recursion.Present the optimized DFS with early stopping.Write clean, tested code and analyze complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Optimize: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal, handling cycles, and efficient exploration of nodes.

Common Follow-ups

• What if rooms contain duplicate keys? → Use a visited set to avoid revisiting.
• Can you solve this iteratively? → Yes, BFS or DFS with stack.
• What if the graph is very large? → Use iterative BFS to avoid stack overflow.
• How to detect unreachable rooms? → Check if visited count equals total rooms.

💡 These follow-ups test your ability to adapt your solution to variations and constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves rooms or nodes with keys or edges; 2) Need to check if all nodes reachable; 3) Graph traversal required; 4) Keys represent edges to other nodes.

Signature Phrases

You start in room 0Each room has keys to other roomsCan you visit all rooms?

NOT This Pattern When

Problems about shortest path or weighted graphs are different patterns.

Similar Problems

Course Schedule - both involve graph traversal and reachabilityNumber of Islands - DFS/BFS traversal to explore connected components

Practice

1. You are given an n x n grid where each cell is either 0 (walkable) or 1 (blocked). You need to find the shortest path from the top-left corner to the bottom-right corner, moving in 8 possible directions (including diagonals). Which algorithmic approach guarantees finding the shortest path efficiently in this scenario?

easy

A. Breadth-First Search (BFS) using a queue to explore neighbors level by level

B. Depth-First Search with backtracking to explore all paths

C. Greedy Best-First Search prioritizing cells closest to the target

D. Dynamic Programming to store shortest paths to each cell

Solution

1. Step 1: Understand the problem constraints

   The grid allows movement in 8 directions and requires the shortest path from start to end.

2. Step 2: Identify the algorithm that guarantees shortest path in unweighted graphs

   BFS explores neighbors level by level, ensuring the first time we reach the target is via the shortest path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS is the classic shortest path algorithm for unweighted grids [OK]

Hint: Shortest path in unweighted grid -> BFS [OK]

Common Mistakes:

• Thinking DFS finds shortest path
• Using greedy heuristics without guarantees

2. Consider the following Python code implementing bidirectional BFS for the Word Ladder problem. Given beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], what is the returned value?

easy

A. 4

B. 5

C. 6

D. 0

Solution

1. Step 1: Trace initial sets and level

   begin_set = {"hit"}, end_set = {"cog"}, level = 1

2. Step 2: Expand begin_set neighbors and check for intersection

   Level 2: neighbors of "hit" include "hot"; no intersection yet. Level increments to 2.

3. Step 3: Expand smaller frontier each iteration until intersection

   Level 3: from "hot" neighbors "dot", "lot"; still no intersection. Level 4: from "dot", "lot" neighbors "dog", "log"; next level neighbors include "cog" which is in end_set, so return level + 1 = 4.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest transformation length is 4 steps [OK]

Hint: Bidirectional BFS returns shortest path length 4 [OK]

Common Mistakes:

• Off-by-one in level counting
• Not updating visited correctly
• Returning 0 if endWord missing

3. What is the time complexity of the optimal BFS approach for the Pacific Atlantic Water Flow problem on an m x n grid, and why?

medium

A. O(m * n) because each cell is enqueued and processed at most once per ocean.

B. O(m * n * log(m * n)) due to priority queue operations in BFS.

C. O(m^2 * n^2) because BFS is run from every cell.

D. O(m + n) because BFS only processes border cells.

Solution

1. Step 1: Analyze BFS visits

   Each BFS starts from border cells and visits each cell at most once per ocean, so total visits ≤ 2 * m * n.

2. Step 2: Confirm no repeated work

   Visited arrays prevent revisiting cells, so BFS complexity is linear in number of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each cell processed once per ocean -> O(m*n) [OK]

Hint: BFS visits each cell once per ocean [OK]

Common Mistakes:

• Confusing with brute force DFS from every cell
• Assuming BFS uses priority queue

4. Consider the following buggy code snippet from the BFS approach for Pacific Atlantic Water Flow. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line that appends (0, j) to pacific_queue

B. Missing line that sets atlantic_reachable[m-1][j] = True

C. Line that sets pacific_reachable[0][j] = True

D. Line that appends (m-1, j) to atlantic_queue

Solution

1. Step 1: Check border initialization

   Both oceans' reachable arrays must mark all border cells as True initially.

2. Step 2: Identify missing marking

   For atlantic ocean, bottom row cells (m-1, j) are added to queue but not marked reachable, causing BFS to miss them.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing atlantic_reachable[m-1][j] = True causes incomplete results [OK]

Hint: All border cells must be marked reachable initially [OK]

Common Mistakes:

• Forgetting to mark atlantic_reachable bottom row
• Marking visited after BFS causes infinite loops

5. What is the time complexity of the bidirectional BFS algorithm for finding the shortest path in an n x n binary matrix, assuming all cells are walkable (0)?

medium

A. O(n^4) because each BFS can explore all cells and edges

B. O(8^(n^2)) due to 8 possible moves from each cell

C. O(n^2) because BFS explores each cell at most once from both ends

D. O(n^3) because of nested loops over rows, columns, and directions

Solution

1. Step 1: Identify number of vertices and edges

   Grid has n^2 vertices; each vertex has up to 8 edges.

2. Step 2: Analyze BFS complexity

   BFS visits each vertex once; total edges processed is O(8*n^2) = O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional BFS halves search space but still O(n^2) [OK]

Hint: BFS in grid -> O(n²) due to vertices and edges [OK]

Common Mistakes:

• Confusing exponential moves with complexity
• Assuming nested loops multiply to n^3 or n^4