Problem 22.8 · Depth-First SearchMedium

Keys and Rooms

What it teaches: Reachability from one node: is every node visited?

Practise it on judges as “Keys and Rooms”.

The problem

Room 0 is unlocked. rooms[i] lists the keys found in room i. Return true if you can enter every room.

Example 1

Input: rooms = [[1],[2],[3],[]]
Output: true

Example 2

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false

Constraints

2 ≤ n ≤ 1000

Pattern clues in the wording

→ Can everything be reached from a start?

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	rooms = [[1],[2],[3],[]]	true
2	rooms = [[1,3],[3,0,1],[2],[0]]	false

From slow to fast

Approaches

1. Iterative DFS · O(rooms + keys)

Iterative DFS

Time O(rooms + keys) Space O(rooms)

Stack starting with 0. Pop a room, push keys to unvisited rooms. Compare the visited count with n.

Approach 1

import java.util.*;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        seen[0] = true;
        int visited = 1;
        while (!stack.isEmpty()) {
            for (int key : rooms.get(stack.pop())) {
                if (seen[key]) continue;
                seen[key] = true;
                visited++;
                stack.push(key);
            }
        }
        return visited == rooms.size();
    }
}

Verdict: Directly the reachability question.

Before you submit

Edge cases and common mistakes

Test these inputs

Room 0 has no keys
Keys to already-open rooms

Mistakes people make

Treating keys as undirected edges.

Interview

Follow-up questions

What is the smallest number of extra keys to make every room reachable?

Command Palette

The problem

Approaches

Iterative DFS

Edge cases and common mistakes

Follow-up questions