We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Keys and Rooms

Number: 871

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Walmart Labs, Tinkoff

Problem Description

You are given n rooms labeled from 0 to n - 1. Initially, only room 0 is unlocked. Each room i contains a list of keys to other rooms represented by rooms[i]. You need to determine whether it is possible to visit every room starting from room 0 by using the keys found along the way.

Key Insights

  • Treat each room as a node in a directed graph and each key as an edge leading to another room.
  • The problem can be solved using graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS).
  • Use a data structure (stack or queue) to traverse through reachable rooms and a visited set or list to keep track of which rooms have been accessed.
  • After the traversal, if the number of visited rooms equals the total number of rooms, then all rooms are reachable.

Space and Time Complexity

Time Complexity: O(N + E) where N is the number of rooms and E is the total number of keys. Space Complexity: O(N) due to the visited data structure and the recursion stack or iterative stack/queue used during traversal.

Solution

We start from room 0 and implement a DFS/BFS to traverse the graph created by the rooms. For each room accessed, we mark it as visited and add all its keys (rooms reachable) to our traversal stack/queue if they are not already visited. Once no more rooms are available to explore, we check if the total number of visited rooms equals the number of rooms provided. If they match, return true; otherwise, return false.

Code Solutions

# Python solution using DFS with a stack
def canVisitAllRooms(rooms):
    # Stack to manage the rooms to visit
    stack = [0]
    # Set to track visited rooms
    visited = set([0])
    
    # Process the stack until no more rooms to visit
    while stack:
        room = stack.pop()  # Get the current room
        for key in rooms[room]:
            if key not in visited:
                visited.add(key)  # Mark the room as visited
                stack.append(key)  # Add the room to the stack for further exploration
    # Return true if all rooms are visited
    return len(visited) == len(rooms)

# Example usage:
rooms = [[1],[2],[3],[]]
print(canVisitAllRooms(rooms))  # Outputs: True
← Back to All Questions