Keys and Rooms

📋

Problem

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?

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

Edge cases: Only one room with no keys → trueRooms with no keys leading anywhere → false if not all visitedRooms with keys pointing back to already visited rooms → should not cause infinite loops

</>

IDE

def canVisitAllRooms(rooms: list[list[int]]) -> bool:public boolean canVisitAllRooms(List<List<Integer>> rooms)bool canVisitAllRooms(vector<vector<int>>& rooms)function canVisitAllRooms(rooms)

def canVisitAllRooms(rooms):
    # Write your solution here
    pass

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool canVisitAllRooms(vector<vector<int>>& rooms) {
    // Write your solution here
    return false;
}

function canVisitAllRooms(rooms) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Not marking visited rooms correctly, causing premature false return.✅ Use a visited set and mark rooms as visited immediately upon entering.

Wrong: Assuming all rooms are reachable without verifying after traversal.✅ After traversal, check if visited set size equals number of rooms before returning true.

Wrong: infinite loop or stack overflowNot handling cycles properly, revisiting rooms endlessly.✅ Use a visited set to skip already visited rooms during traversal.

Wrong: timeoutUsing exponential or repeated traversals without visited set.✅ Implement DFS or BFS with visited set to achieve O(N+E) time complexity.

✓

Test Cases

Focus on handling minimal inputs and cycles to avoid infinite loops.

Watch out for greedy traps and ensure full graph traversal.

Optimize your solution to linear time complexity using visited sets.

t1_01basic

Input{"rooms":[[1],[2],[3],[]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

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.

💡 Think about traversing rooms starting from room 0 using keys found.

💡 Use DFS or BFS to track which rooms can be visited.

💡 Mark rooms as visited when you enter them to avoid revisiting.

Why it failed: Returned false but all rooms are reachable from room 0. Fix by correctly marking visited rooms and exploring all keys.

✓ Correctly identifies all reachable rooms from room 0.

t1_02basic

Input{"rooms":[[1,3],[3,0,1],[2],[0]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Room 2 is only reachable from itself and is not accessible from room 0. Not all rooms can be visited.

💡 Check if all rooms are reachable from room 0 by traversing keys.

💡 Ensure you do not revisit rooms unnecessarily but also do not miss any reachable room.

💡 Return false if any room is not visited after traversal.

Why it failed: Returned true but room 2 is unreachable from room 0. Fix by verifying all rooms are visited after traversal.

✓ Correctly detects unreachable rooms and returns false.

t2_01edge

Input{"rooms":[[]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Only one room with no keys. Starting room 0 is visited, so all rooms are visited.

💡 Consider the smallest input where only one room exists.

💡 Check if the algorithm handles single-element input correctly.

💡 Return true if the only room (room 0) is visited.

Why it failed: Returned false for single room with no keys. Fix by handling base case where n=1 and room 0 is trivially visited.

✓ Correctly handles single room with no keys.

t2_02edge

Input{"rooms":[[1],[],[]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Room 2 is unreachable because room 1 has no keys. Not all rooms can be visited.

💡 Check if traversal stops prematurely when no keys are found in a room.

💡 Verify that all rooms are visited after traversal, not just those reachable in one step.

💡 Return false if any room remains unvisited.

Why it failed: Returned true despite unreachable room 2. Fix by ensuring traversal explores all reachable rooms and checks completeness.

✓ Correctly identifies unreachable rooms and returns false.

t2_03edge

Input{"rooms":[[1],[0]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Rooms 0 and 1 have keys to each other, forming a cycle. Both rooms are reachable.

💡 Detect and handle cycles to avoid infinite loops.

💡 Use a visited set to prevent revisiting rooms endlessly.

💡 Return true if all rooms are visited despite cycles.

Why it failed: Algorithm enters infinite loop or stack overflow due to cycles. Fix by using a visited set to track visited rooms.

✓ Correctly handles cycles and returns true.

t3_01corner

Input{"rooms":[[1],[2],[3],[4],[5],[6],[7],[8],[9],[]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Linear chain of rooms from 0 to 9, each room has key to next. All rooms reachable.

💡 Check if your traversal correctly visits all rooms in a chain.

💡 Avoid greedy approaches that stop early after finding some keys.

💡 Ensure traversal continues until no new rooms can be visited.

Why it failed: Returned false due to greedy stopping early or incomplete traversal. Fix by fully exploring all reachable rooms.

✓ Correctly traverses linear chain and returns true.

t3_02corner

Input{"rooms":[[1,2],[3],[3],[]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Multiple keys to same room 3 from different rooms. Should not revisit room 3 multiple times.

💡 Avoid revisiting rooms already visited to prevent infinite loops.

💡 Use a visited set to track rooms and skip revisits.

💡 Return true if all rooms are visited once.

Why it failed: Algorithm revisits rooms causing infinite loops or stack overflow. Fix by checking visited before recursive calls.

✓ Correctly handles multiple keys to same room and returns true.

t3_03corner

Input{"rooms":[[1],[2],[0],[]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Room 3 is isolated with no keys leading to it. Not all rooms can be visited.

💡 Check if isolated rooms without keys are detected as unreachable.

💡 Verify that traversal does not assume all rooms are reachable.

💡 Return false if any room remains unvisited.

Why it failed: Returned true despite isolated room 3. Fix by verifying all rooms visited after traversal.

✓ Correctly detects isolated rooms and returns false.

t4_01performance

Input{"rooms":[[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12],[13],[14],[15],[16],[17],[18],[19],[20],[21],[22],[23],[24],[25],[26],[27],[28],[29],[30],[31],[32],[33],[34],[35],[36],[37],[38],[39],[40],[41],[42],[43],[44],[45],[46],[47],[48],[49],[50],[51],[52],[53],[54],[55],[56],[57],[58],[59],[60],[61],[62],[63],[64],[65],[66],[67],[68],[69],[70],[71],[72],[73],[74],[75],[76],[77],[78],[79],[80],[81],[82],[83],[84],[85],[86],[87],[88],[89],[90],[91],[92],[93],[94],[95],[96],[97],[98],[99],[]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 rooms in a linear chain, O(N+E) traversal must complete within 2 seconds.

💡 Use DFS or BFS with a visited set for O(N+E) complexity.

💡 Avoid exponential or repeated traversals that cause TLE.

💡 Efficient graph traversal algorithms run in linear time.

Why it failed: TLE due to exponential or repeated traversals. Fix by using visited set and linear time DFS/BFS.

✓ Algorithm runs in O(N+E) time and passes performance test.

Practice

1. You are given a directed acyclic graph with n nodes and a list of edges. You want to find the smallest set of nodes such that starting a traversal from these nodes can reach every other node in the graph. Which approach guarantees finding this minimal set efficiently?

easy

A. Perform BFS from each node and pick the nodes that can reach all others.

B. Identify all nodes with zero in-degree and return them as the minimal set.

C. Identify all nodes with zero in-degree and return them as the minimal set.

D. Use a dynamic programming approach to count paths from each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires the minimal set of vertices from which all nodes are reachable. Nodes with zero in-degree are exactly those that no other node reaches, so they must be included.

2. Step 2: Analyze approaches

   Performing BFS from each node is inefficient. Dynamic programming counting paths is unnecessary. The minimal set is precisely all nodes with zero in-degree.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Minimal set corresponds exactly to zero in-degree nodes [OK]

Hint: Minimal set corresponds exactly to zero in-degree nodes [OK]

Common Mistakes:

• Assuming BFS from each node is efficient
• Confusing zero in-degree nodes with minimal set without justification
• Using DP which is unnecessary here

2. Consider the following Python code implementing the Bellman-Ford algorithm for the Network Delay Time problem. Given the input times = [[1,2,1],[2,3,2],[1,3,4]], n = 3, and k = 1, what is the final returned value?

easy

A. 4

B. 3

C. 2

D. -1

Solution

1. Step 1: Initialize distances with dist[1]=0, dist[2]=inf, dist[3]=inf

   After first iteration, relax edges: dist[2]=1 (via 1->2), dist[3]=4 (via 1->3)

2. Step 2: Second iteration relaxes edge 2->3: dist[3] updated to dist[2]+2=3 which is less than 4

   No further updates after this iteration, so loop breaks early

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maximum distance is 3, so return 3 [OK]

Hint: Relax edges repeatedly until no updates or n-1 iterations [OK]

Common Mistakes:

• Not updating dist[3] to 3 after second iteration
• Returning initial max distance 4 instead of updated 3
• Confusing iteration count and stopping early

3. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

4. What is the time complexity of the optimal Dijkstra's algorithm variant solution for the minimum effort path problem on an n x m grid?

medium

A. O(n * m^2)

B. O(n * m * log(n * m))

C. O((n * m)^2)

D. O(n * m)

Solution

1. Step 1: Identify graph size

   The grid has n*m nodes and up to 4 edges per node, so edges E = O(n*m).

2. Step 2: Analyze Dijkstra's complexity

   Using a min-heap, each node is pushed/popped at most once, heap operations cost O(log(n*m)), total O(n*m*log(n*m)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Log factor comes from heap operations on n*m nodes [OK]

Hint: Dijkstra on grid -> O(V log V) with V=n*m [OK]

Common Mistakes:

• Confusing edges with nodes count
• Assuming O(n*m^2) due to nested loops
• Ignoring log factor from heap

5. Suppose the problem is modified so that islands can be connected diagonally as well (8-direction connectivity). Which of the following changes to the DFS approach correctly counts islands under this new rule?

hard

A. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to the DFS calls in addition to the four cardinal directions.

B. Keep the DFS calls unchanged but count diagonally adjacent '1's separately after DFS completes.

C. Use BFS instead of DFS without changing neighbor directions, as BFS handles diagonal connectivity automatically.

D. Modify the grid to mark diagonal neighbors as '1' before running the original DFS.

Solution

1. Step 1: Understand the new connectivity rule

   Islands now connect horizontally, vertically, and diagonally, so DFS must explore all 8 neighbors.

2. Step 2: Modify DFS to include diagonal neighbors

   Add recursive DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), and (r-1,c-1) along with the original four directions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only adding diagonal neighbors to DFS ensures correct island counting with 8-direction connectivity [OK]

Hint: Add diagonal neighbors to DFS for 8-direction connectivity [OK]

Common Mistakes:

• Assuming BFS handles diagonals without code change
• Counting diagonals separately after DFS