Keys and Rooms

Medium

Asked by:

39 views

Topics:

Graphs

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example 1:

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

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

How is the list of rooms represented? Is it a list of lists of integers, where each integer represents a key that unlocks a specific room?
What is the range of room numbers? Are they guaranteed to be contiguous starting from 0, or can there be gaps? Are there any limits on the number of rooms or keys?
Can a key unlock the room it's found in? Can a room contain a key to itself?
Can a key appear multiple times across different rooms? Can a room have multiple keys that unlock the same room?
If it's impossible to visit all rooms, should I return `false`, or is there any other specific value I should return?

Brute Force Solution

Approach

The brute force approach to the keys and rooms problem involves trying every possible path through the rooms. We start at the first room and explore all the keys we find to unlock other rooms. We repeat this process, exploring new rooms as we unlock them, until we have either visited all rooms or run out of new rooms to explore.

Here's how the algorithm would work step-by-step:

Start in the first room.
Check what keys are in that room.
For each key, see if it unlocks a new room that hasn't been visited yet.
If it does, go to that new room.
Repeat the process of checking keys and unlocking rooms in the new room.
Keep doing this until you can't find any new rooms to unlock from the rooms you've already visited.
At the end, check if you have visited all the rooms. If so, you're done. If not, this particular path didn't work.

Code Implementation

def canVisitAllRooms(rooms): 
    number_of_rooms = len(rooms)
    visited_rooms = [False] * number_of_rooms
    visited_rooms[0] = True
    rooms_to_visit = [0]

    while rooms_to_visit:
        current_room = rooms_to_visit.pop(0)

        # Iterate through the keys in the current room.
        for key in rooms[current_room]:
            # Avoid infinite loops by visiting each room only once.
            if not visited_rooms[key]:
                visited_rooms[key] = True

                # Queue up the newly unlocked room for exploration
                rooms_to_visit.append(key)

    # Check if all rooms have been visited.
    return all(visited_rooms)

Big(O) Analysis

Time Complexity

O(n!) – In the worst-case scenario, we might explore all possible permutations of rooms. Starting from room 0, we could potentially unlock any of the remaining n-1 rooms. From each of those rooms, we could unlock any of the remaining rooms, and so on. This results in a factorial number of paths (n!) being explored in the worst-case, where n is the number of rooms. Therefore, the time complexity is O(n!).

Space Complexity

O(N) – The algorithm implicitly uses a visited set (or similar data structure) to keep track of which rooms have already been visited to avoid cycles. In the worst-case scenario, we might need to visit all N rooms before determining if all rooms are reachable. Thus, the size of the visited set can grow up to N. No other significant auxiliary space is utilized.

Optimal Solution

Approach

The goal is to determine if you can unlock all rooms, starting from room 0. We can think of this as exploring a maze where each room contains keys to other rooms. We'll use a method similar to how you might explore a real maze, marking off the rooms you've already been to so you don't waste time going in circles.

Here's how the algorithm would work step-by-step:

Start at room 0. This is our initial location.
Keep track of all the rooms you've visited. Initially, only room 0 has been visited.
Look at the keys in your current room. Each key lets you access another room.
For each key, if you haven't visited the room it unlocks, go to that room and mark it as visited.
Repeat the process of looking at keys and visiting new rooms until you've run out of new rooms to visit.
Once you've explored as much as possible, check if you've visited all the rooms. If you have, you can unlock all the rooms; otherwise, you can't.

Code Implementation

def can_visit_all_rooms(rooms):
    number_of_rooms = len(rooms)
    visited_rooms = [False] * number_of_rooms

    # Start from room 0
    visited_rooms[0] = True
    rooms_to_visit = [0]

    while rooms_to_visit:
        current_room = rooms_to_visit.pop()

        # Explore keys in the current room
        for key in rooms[current_room]:
            # Visit unvisited rooms
            if not visited_rooms[key]:
                visited_rooms[key] = True
                rooms_to_visit.append(key)

    #Check if all rooms were visited
    return all(visited_rooms)

Big(O) Analysis

Time Complexity

O(n + e) – We visit each of the n rooms at most once. For each room we visit, we iterate through the keys it contains. If we consider the rooms as nodes in a graph and the keys as edges, we can say there are e edges in total. Thus, the time complexity is determined by the number of nodes (rooms) and the number of edges (keys). Therefore, the overall time complexity is O(n + e), where n is the number of rooms and e is the total number of keys (edges between rooms).

Space Complexity

O(N) – The algorithm uses a visited set to keep track of the rooms that have already been visited, where N is the total number of rooms. In the worst-case scenario, we might visit all the rooms, leading to the visited set containing N elements. The size of the visited set determines the auxiliary space used. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
rooms is null or empty	Return true immediately, as there are no rooms to visit, fulfilling the condition trivially.
rooms contains only one room with no keys	Return true, because we start in room 0, which is the only room.
A room's key list is empty	The algorithm should still function correctly, as the empty key list simply means we don't unlock any new rooms from that room.
Rooms contain cycles (e.g., room A has key to B, room B has key to A)	The visited set prevents infinite loops by tracking visited rooms.
Rooms are unreachable from room 0	The algorithm correctly identifies that not all rooms can be visited and returns false.
Maximum number of rooms to test scalability	The solution's time complexity, O(N+E) where N is the number of rooms and E is the number of keys (edges), makes it relatively scalable.
A room contains a key to itself	The algorithm correctly ignores this self-referential key by using a visited set.
Integer overflow if key values are very large, but within integer range	Keys represent room indices, so overflow isn't directly applicable since we're not performing arithmetic with them beyond indexing into the rooms array.

rooms is null or empty

How to Handle:

Return true immediately, as there are no rooms to visit, fulfilling the condition trivially.

rooms contains only one room with no keys

How to Handle:

Return true, because we start in room 0, which is the only room.

A room's key list is empty

How to Handle:

The algorithm should still function correctly, as the empty key list simply means we don't unlock any new rooms from that room.

Rooms contain cycles (e.g., room A has key to B, room B has key to A)

How to Handle:

The visited set prevents infinite loops by tracking visited rooms.

Rooms are unreachable from room 0

How to Handle:

The algorithm correctly identifies that not all rooms can be visited and returns false.

Maximum number of rooms to test scalability

How to Handle:

The solution's time complexity, O(N+E) where N is the number of rooms and E is the number of keys (edges), makes it relatively scalable.

A room contains a key to itself

How to Handle:

The algorithm correctly ignores this self-referential key by using a visited set.

Integer overflow if key values are very large, but within integer range

How to Handle:

Keys represent room indices, so overflow isn't directly applicable since we're not performing arithmetic with them beyond indexing into the rooms array.