https://leetcode.com/problems/keys-and-rooms

The main idea you need to understand to solve this problem that it is a graph problem. We have list of rooms - nodes and for each room you have list of keys, this is edges which go from this node. Problem is asking if you can traverse all graph, starting from node 0. As usual, there are different ways to do it:

  1. iterative dfs with stack
  2. recursive dfs without explicit stack (however we have implicit stack)
  3. bfs, using queue.

Whenever I can I choose recursive dfs, because it is the easiest to code: we keep set of visited nodes, and for dfs(room) we try to visit all new rooms which we can open with keys, which we did not visit yet, run then to visited set and run dfs recursively. In the end we check that length of visited set is equal to length of total number of rooms.

Complexity: time complexity is O(N+E), where N is number of rooms ans E is total number of keys. Space complexity is O(N) - size of visited and size of implicit stack as well.

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = set([0])
        
        def dfs(room):
            for neib in rooms[room]:
                if neib not in visited:
                    visited.add(neib)
                    dfs(neib)
                    
        dfs(0)
        return len(visited) == len(rooms)

Oneliner, just for fun:

Idea is to construct adjacency matrix and then use matrix exponent to understand if we can reach nodes or not.

from scipy.sparse.linalg import expm

class Solution:
    def canVisitAllRooms(self, rooms):
        return 0 not in expm([[j in r + [i] for j in range(len(rooms))] for i,r in enumerate(rooms)])[0]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0841