Medium

Keys and Rooms

LAB

Rooms are encoded as rows of keys found inside each room. Starting from room 0, return true if every room can be visited.

EXAMPLES

Example 1

Input
{
  "rooms": [
    [
      1
    ],
    [
      2
    ],
    [
      3
    ],
    []
  ]
}

Output
true

FUNCTION SHAPE

rooms: intMatrix→bool

SOLUTION NOTE

Very simple.

Reveal reference solution +

pythonREFERENCE

# dfs. visited
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    visited = set()

    def dfs(room):
        if room in visited: return
        visited.add(room)

        for key in rooms[room]:
            dfs(key)

    dfs(0)
    return len(visited) == len(rooms)

TimeO(n + k)

SpaceO(n)

Open on LeetCode ↗