#841

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Keys and Rooms

Determine if all rooms can be visited given keys distributed across a set of interconnected locked rooms using graph traversal.

depth first search breadth first search graph

Problem Statement

You are given n rooms labeled from 0 to n - 1, all locked except room 0. Each room may contain keys to other rooms. Starting from room 0, determine whether it is possible to visit every room by collecting keys as you go. A key for a room allows immediate access to that room and any keys found there can be used subsequently.

Given an array rooms where rooms[i] is a list of distinct keys found in room i, return true if you can eventually enter every room, or false if some rooms remain locked. The keys can unlock rooms in any order, but each room must be accessible directly or indirectly from room 0 to succeed.

Examples

Example 1

Input: rooms = [[1],[2],[3],[]]

Output: true

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

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.

Solution Approach

Depth-First Search (DFS) Traversal

Start at room 0 and recursively visit all rooms for which you have keys. Mark visited rooms to prevent cycles. If all rooms are marked visited after DFS, return true. This method directly maps the problem to graph traversal nodes and edges.

Breadth-First Search (BFS) Traversal

Use a queue to process rooms starting from room 0. For each room dequeued, add unvisited rooms corresponding to keys found into the queue. Continue until no more rooms are left to explore. Verify if all rooms have been visited to decide the result.

Visited Set Optimization

Maintain a set or boolean array to track visited rooms. Only add keys that unlock unvisited rooms to the traversal to avoid redundant processing. This reduces unnecessary exploration and ensures O(N + E) time complexity.

Complexity Analysis

Metric	Value
Time	O(N + E)
Space	O(N)

The traversal must visit each room once and process all keys once. With N rooms and E total keys, time complexity is O(N + E). Space complexity is O(N) to track visited rooms.

What Interviewers Usually Probe

Looks for a correct graph traversal mapping and edge handling.
Checks if DFS and BFS alternatives are considered for visiting all rooms.
Wants awareness of cycles and revisiting rooms when keys overlap.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark rooms as visited leading to infinite loops or redundant work.
Assuming keys must be used in numerical order instead of exploring available keys flexibly.
Not handling rooms with no keys correctly, which can block traversal if not checked.

Follow-up variants

Rooms may contain multiple keys for the same room, requiring careful visited tracking.
Rooms can form disconnected components; determine accessibility from room 0 only.
Keys could be nested or recursive, requiring iterative or recursive traversal strategies.

FAQ

What is the main strategy to solve Keys and Rooms?

The primary approach is graph traversal using DFS or BFS to visit all rooms starting from room 0 and collecting keys.

Can BFS be used instead of DFS for this problem?

Yes, BFS works equally well by processing rooms level by level using a queue while tracking visited rooms.

What if some rooms contain no keys?

Rooms with no keys are still counted as visited once entered. They must be marked visited to ensure correct traversal.

How do I avoid revisiting rooms unnecessarily?

Maintain a visited set or boolean array. Only add keys for unvisited rooms to the traversal structure.

What pattern does this problem exemplify?

Keys and Rooms exemplifies graph traversal with depth-first search pattern and the challenge of visiting all nodes in a connected graph with constraints.

terminal

Solution

Solution 1: Depth-First Search (DFS)

We can use the Depth-First Search (DFS) method to traverse the entire graph, count the number of reachable nodes, and use an array `vis` to mark whether the current node has been visited to prevent repeated visits.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(i: int):
            if i in vis:
                return
            vis.add(i)
            for j in rooms[i]:
                dfs(j)

        vis = set()
        dfs(0)
        return len(vis) == len(rooms)

Solution 2: BFS

We can also use the Breadth-First Search (BFS) method to traverse the entire graph. We use a hash table or an array `vis` to mark whether the current node has been visited to prevent repeated visits.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(i: int):
            if i in vis:
                return
            vis.add(i)
            for j in rooms[i]:
                dfs(j)

        vis = set()
        dfs(0)
        return len(vis) == len(rooms)

Continue Practicing

#802 find eventual safe states #797 all paths from source to target #886 possible bipartition