#841 - Keys and Rooms

MediumGraphs - DFS

There are n rooms labeled 0 to n - 1. All rooms are locked except room 0. Each room may contain keys to other rooms. Given rooms where rooms[i] is the set of keys in room i, return true if you can visit all rooms.

Input	Output
rooms = [[1],[2],[3],[]]	true
rooms = [[1,3],[3,0,1],[2],[0]]	false

Solution Space

Try it

/**
 * Returns true if all rooms can be visited starting from room 0.
 *
 * @param rooms rooms[i] = list of keys found in room i
 * @returns Whether all rooms are reachable
 */
export function canVisitAllRooms(rooms: number[][]): boolean {
  const visited = new Set<number>();
  const stack: number[] = [0];

  while (stack.length > 0) {
    const room = stack.pop()!;
    if (visited.has(room)) continue;
    visited.add(room);

    for (const key of rooms[room]) {
      if (!visited.has(key)) stack.push(key);
    }
  }

  return visited.size === rooms.length;
}

Approach: iterative DFS – start from room 0, use a stack to explore reachable rooms, track visited rooms in a Set.

Time: O(n + e) – where n is number of rooms and e is total number of keys.

Space: O(n) – visited set and stack.

#547 Number of Provinces

#1466 Reorder Routes to Make All Paths Lead to the City Zero