How hard is LeetCode 841. Keys and Rooms?

LeetCode 841. Keys and Rooms is rated Medium on LeetCode.

What is the time complexity of LeetCode 841. Keys and Rooms?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 841. Keys and Rooms?

The Python solution on this page uses O(n), where n is the number of nodes, and m is the number of edges auxiliary space.

What topics does LeetCode 841. Keys and Rooms cover?

LeetCode 841. Keys and Rooms is tagged Depth-First Search, Breadth-First Search and Graph on LeetCode.

Keys and Rooms — LeetCode 841 Python Solution

MediumDepth-First SearchBreadth-First SearchGraph

Problem: #841
Pattern: Breadth-First Search
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: We visit room 0 and pick up key 1.

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n), where n is the number of nodes, and m is the number of edges auxiliary

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 841. Keys and Rooms is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

On a study list

This problem is on LeetCode 75.

Frequently asked questions

How hard is LeetCode 841. Keys and Rooms?: LeetCode 841. Keys and Rooms is rated Medium on LeetCode.
What is the time complexity of LeetCode 841. Keys and Rooms?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 841. Keys and Rooms?: The Python solution on this page uses O(n), where n is the number of nodes, and m is the number of edges auxiliary space.
What topics does LeetCode 841. Keys and Rooms cover?: LeetCode 841. Keys and Rooms is tagged Depth-First Search, Breadth-First Search and Graph on LeetCode.