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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Keys and Rooms

Difficulty: Medium

Problem Description

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.

Key Insights

  • You start in room 0, which is unlocked.
  • Each room contains keys to other rooms, which can be used to unlock additional rooms.
  • The problem can be modeled as a graph where rooms are nodes and keys are edges.
  • A depth-first search (DFS) or breadth-first search (BFS) can be used to explore reachable rooms.

Space and Time Complexity

Time Complexity: O(n + e), where n is the number of rooms and e is the total number of keys (edges). Space Complexity: O(n), for the visited array and the stack/queue used in DFS/BFS.

Solution

To solve this problem, we can utilize either a Depth-First Search (DFS) or Breadth-First Search (BFS) approach. We will maintain a visited list to track which rooms have been accessed. Starting from room 0, we will explore all reachable rooms and collect the keys found in each room. For each key, if it unlocks a room that hasn't been visited yet, we will continue the search. If we manage to visit all rooms, we return true; otherwise, we return false.

Code Solutions

def canVisitAllRooms(rooms):
    visited = [False] * len(rooms)
    visited[0] = True
    stack = [0]

    while stack:
        room = stack.pop()
        for key in rooms[room]:
            if not visited[key]:
                visited[key] = True
                stack.append(key)

    return all(visited)
← Back to All Questions