algoadvance

Leetcode 841. Keys and Rooms

Problem Statement

There are N rooms and you start in room 0. Each room has a list of keys to other rooms. Initially, all rooms are locked except for room 0.

You can move freely between rooms as long as you have the key for that room.

Write a function to determine if you can visit all the rooms.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation: 
We start in room 0 and pick up the key to room 1.
We then go to room 1 and pick up the key to room 2.
We then go to room 2 and pick up the key to room 3.
We then go to room 3. Since we were able to visit every room, the output is true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room 2 since the only key to it is in room 1.

Note:

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. The number of keys in all rooms combined <= 3000.

Clarifying Questions

Before proceeding, let’s make sure we have everything covered:

  1. Can a room contain multiple keys to the same room?
    • Yes, a room can contain multiple keys to the same room.
  2. Is it guaranteed that each key leads to a different room?
    • No, a key can lead to any room (including the current room or already visited rooms).
  3. Should we consider cycles?
    • Yes, we should account for possible cycles due to keys leading back to already visited rooms.

Strategy

We can approach this problem using a Depth-First Search (DFS) or Breadth-First Search (BFS) strategy. Both approaches will help us explore all reachable rooms starting from room 0. We should maintain a set to keep track of visited rooms to avoid revisiting rooms.

Steps for DFS approach:

  1. Create a set visited to track visited rooms.
  2. Implement a recursive function that explores each room and its keys.
  3. Starting from room 0, visit all rooms reachable using the keys available.
  4. After the traversal, check if the size of the visited set equals the number of rooms.

Code

Here’s how we could implement this in Java:

import java.util.HashSet;
import java.util.List;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        HashSet<Integer> visited = new HashSet<>();
        dfs(rooms, 0, visited);
        return visited.size() == rooms.size();
    }
    
    private void dfs(List<List<Integer>> rooms, int currentRoom, HashSet<Integer> visited) {
        // If already visited, return
        if (visited.contains(currentRoom)) {
            return;
        }
        
        // Mark this room as visited
        visited.add(currentRoom);
        
        // Visit all keys in the current room
        for (int key : rooms.get(currentRoom)) {
            dfs(rooms, key, visited);
        }
    }
}

Time Complexity

The time complexity of this approach is O(V + E), where:

This is because we are visiting each room once and exploring each key once during the DFS traversal.

The space complexity is also O(V) due to the recursion stack and the visited set storing the rooms.

This solution ensures we effectively explore all accessible rooms starting from room 0, and finally, we check if every room has been visited to determine if we can visit all rooms.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI