algoadvance

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the other rooms.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v allows you to enter room v directly.

Initially, all the rooms start locked except for room 0.

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

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

Example 2:

Input: [[1,3], [3,0,1], [2], [0]]
Output: false
Explanation: We can't enter the room with number 2.

Constraints:

• 1 <= rooms.length <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < rooms.length
• All the values of rooms[i] are unique.

Clarifying Questions

1. Are the keys in each room guaranteed to point to valid room numbers?
   • Yes, we can assume that all keys are valid room numbers within the range [0, N-1].
2. Can a room have multiple keys to the same room?
   • It is assumed that all the keys in rooms are unique.

Strategy

We’ll use a Breadth-First Search (BFS) or Depth-First Search (DFS) approach to explore the rooms starting from room 0. The goal is to see if we can visit all the rooms by collecting and using keys found in each room.

Steps:

1. Initialize a set to track visited rooms.
2. Use a stack or queue to manage the rooms to explore next.
3. Start by adding room 0 to the stack/queue.
4. Iterate while there are rooms to explore:
   • Pop a room from the stack/queue.
   • For each key in the current room, if the corresponding room has not been visited, add it to the stack/queue.
5. If we have visited all rooms, return true. Otherwise, return false.

Choice of Data Structures:

• We’ll use a set for visited rooms as it ensures O(1) complexity for membership checks.
• Stack/queue can be either list (for stack) or collections.deque (for queue).

Code

def canVisitAllRooms(rooms):
    N = len(rooms)
    visited = set()
    stack = [0]  # start with room 0
    
    while stack:
        current_room = stack.pop()
        if current_room not in visited:
            visited.add(current_room)
            for key in rooms[current_room]:
                if key not in visited:
                    stack.append(key)
    
    return len(visited) == N

# Example usage:
print(canVisitAllRooms([[1], [2], [3], []]))  # Output: True
print(canVisitAllRooms([[1,3], [3,0,1], [2], [0]]))  # Output: False

Time Complexity

The time complexity of the algorithm is O(N + E), where:

• N is the number of rooms.
• E is the total number of keys across all rooms.

We visit each room at most once and explore each key at most once.

Space Complexity

The space complexity is also O(N + E), which includes the space for the visited set and the stack.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?