Keys and Rooms

• Initialize a Set<Integer> named visited and add 0 to it.
• Initialize a Set<Integer> named keys and add all keys from rooms.get(0).
• Start a while loop that continues as long as progress is made in visiting new rooms.
• Inside the loop, set a progressMade flag to false.
• Create a temporary copy of the keys set to iterate over, to avoid modification issues while iterating.
• For each key in the copied set:
  • If the room corresponding to key has not been visited:
    • Add the key to the visited set.
    • Add all keys from rooms.get(key) to a temporary newKeysFound set.
    • Set progressMade to true.
• After the inner loop, add all keys from newKeysFound to the main keys set.
• If progressMade is false after a full iteration, break the while loop.
• After the loop terminates, return true if visited.size() equals the total number of rooms, false otherwise.

We use a Set called visited to store the indices of rooms we have entered, and another Set called keys to store all the keys we have collected so far. Initially, we can only enter room 0, so we add 0 to visited and collect all keys from rooms[0], adding them to the keys set. We then enter a loop that continues as long as we are making progress (i.e., visiting new rooms). Inside the loop, we iterate through a copy of our current keys. For each key, if it unlocks a room we haven't visited, we mark that room as visited, collect all the keys from it, and add them to our keys set. If an entire pass through our collected keys results in no new rooms being visited, we know we are stuck and can't explore further, so we break the loop. Finally, we check if the number of rooms in our visited set is equal to the total number of rooms.

1import java.util.HashSet;2import java.util.Set;3import java.util.List;4import java.util.ArrayList;5 6class Solution {7    public boolean canVisitAllRooms(List<List<Integer>> rooms) {8        int n = rooms.size();9        Set<Integer> visited = new HashSet<>();10        Set<Integer> keys = new HashSet<>();11        12        // Start at room 013        visited.add(0);14        keys.addAll(rooms.get(0));15        16        boolean progressMade = true;17        while (progressMade) {18            progressMade = false;19            Set<Integer> newKeysFound = new HashSet<>();20            21            // Iterate over a copy to avoid ConcurrentModificationException22            List<Integer> keysToTry = new ArrayList<>(keys);23 24            for (int key : keysToTry) {25                if (!visited.contains(key)) {26                    visited.add(key);27                    newKeysFound.addAll(rooms.get(key));28                    progressMade = true;29                }30            }31            keys.addAll(newKeysFound);32        }33        34        return visited.size() == n;35    }36}

• Initialize a boolean array visited of size n (number of rooms) to all false.
• Define a recursive function dfs(room, rooms, visited).
• Call dfs(0, rooms, visited) to start the traversal from room 0.
• Inside dfs(room, ...):
  • Mark the current room as visited: visited[room] = true.
  • Get the list of keys for the current room.
  • For each key in the list:
    • If the room key has not been visited (!visited[key]), recursively call dfs(key, rooms, visited).
• After the initial dfs call completes, iterate through the visited array.
• If any element visited[i] is false, return false.
• If the loop completes without finding any unvisited rooms, return true.

The problem can be seen as finding if all nodes in a directed graph are reachable from a starting node (room 0). DFS is a natural fit for this. We use a boolean array visited to keep track of the rooms we have entered. We can implement DFS either recursively or iteratively using a stack. The recursive approach is often more concise. We start the dfs function from room 0. In the function, we first mark the current room as visited. Then, for each key in the current room, we check if the room it unlocks has been visited. If not, we make a recursive call to dfs for that new room. This process continues until we have explored all reachable rooms from room 0. After the initial dfs(0) call returns, we iterate through our visited array. If any room is marked as false, it means it was unreachable, so we return false. If all rooms are true, we return true.

Recursive DFS:

1import java.util.List;2 3class Solution {4    public boolean canVisitAllRooms(List<List<Integer>> rooms) {5        boolean[] visited = new boolean[rooms.size()];6        dfs(0, rooms, visited);7        8        for (boolean roomVisited : visited) {9            if (!roomVisited) {10                return false;11            }12        }13        return true;14    }15    16    private void dfs(int room, List<List<Integer>> rooms, boolean[] visited) {17        if (visited[room]) {18            return;19        }20        visited[room] = true;21        for (int key : rooms.get(room)) {22            dfs(key, rooms, visited);23        }24    }25}

Iterative DFS:

1import java.util.List;2import java.util.Stack;3 4class SolutionIterative {5    public boolean canVisitAllRooms(List<List<Integer>> rooms) {6        boolean[] visited = new boolean[rooms.size()];7        Stack<Integer> stack = new Stack<>();8        9        stack.push(0);10        visited[0] = true;11        int count = 1;12        13        while (!stack.isEmpty()) {14            int u = stack.pop();15            for (int v : rooms.get(u)) {16                if (!visited[v]) {17                    visited[v] = true;18                    stack.push(v);19                    count++;20                }21            }22        }23        24        return count == rooms.size();25    }26}

• Initialize a boolean array visited of size n to all false.
• Initialize a Queue<Integer> and add 0 to it.
• Mark room 0 as visited: visited[0] = true.
• Initialize a counter visitedCount to 1.
• While the queue is not empty:
  • Dequeue a room, let's call it currentRoom.
  • For each key in rooms.get(currentRoom):
    • If room key has not been visited (!visited[key]):
      • Mark it as visited: visited[key] = true.
      • Enqueue the key.
      • Increment visitedCount.
• After the loop, return true if visitedCount equals n, false otherwise.

BFS explores the graph layer by layer from the source node (room 0). This is achieved using a queue data structure. We initialize a Queue and add room 0 to it. We also use a visited array (or set) to avoid processing rooms more than once and to prevent cycles. We mark room 0 as visited and add it to the queue. We also keep a count of visited rooms. The main loop continues as long as the queue is not empty. In each iteration, we dequeue a room. For this room, we iterate through all the keys it contains. For each key, if the corresponding room has not been visited, we mark it as visited, increment our count, and enqueue it. After the loop finishes, all reachable rooms will have been visited. We simply compare our count of visited rooms with the total number of rooms (n). If they match, it means all rooms were reachable.

1import java.util.List;2import java.util.Queue;3import java.util.LinkedList;4 5class Solution {6    public boolean canVisitAllRooms(List<List<Integer>> rooms) {7        int n = rooms.size();8        boolean[] visited = new boolean[n];9        Queue<Integer> queue = new LinkedList<>();10        11        // Start with room 012        visited[0] = true;13        queue.add(0);14        int visitedCount = 1;15        16        while (!queue.isEmpty()) {17            int currentRoom = queue.poll();18            19            for (int key : rooms.get(currentRoom)) {20                if (!visited[key]) {21                    visited[key] = true;22                    queue.add(key);23                    visitedCount++;24                }25            }26        }27        28        return visitedCount == n;29    }30}