Keys and Rooms — Day 100 (Python)

Photo by Darío Martínez-Batlle on Unsplash

Today’s question is from Daily Leetcode Coding Challenge — March Edition. It is a medium-tagged question. Let us look into the problem statement.

841. Keys and Rooms

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3. Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.


  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. The number of keys in all rooms combined is at most 3000.

We have a list of rooms. Each index in the list represents room numbers. Within each room, we have few keys. Except for room 0, we would require keys to enter any other room. We start from room 0, collect the keys present in room 0. Let us keep all the keys that we collect in a queue. We visit the next rooms by taking keys present in our queue. Each time we visit a new room, let us keep all the keys present in this room in the queue.

What about edge cases when Room 1 has the key for Room 2 and Room 2 has the key for Room 1. In such a case, we will have a circular relation. To avoid circular relations, we can make use of a visited list that is of the same size as the number of rooms. The visited list is initialized as False.

This reminds us of BFS algorithm. Let us use BFS to solve this problem.

class CanVisitAllRoomFinder:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
key_queue = []
visited = [False] * len(rooms)
for keys in rooms[0]:
visited[0] = True
out = key_queue.pop(0)
if visited[out] != True:
for keys in rooms[out]:
visited[out] = True
return True if all(visited) else False

Complexity analysis.

Time Complexity

The time complexity for this algorithm is O(N + K), where N is the number of rooms and K is the number of Keys.

Space Complexity

The space complexity is O(N) since we are using a list to store the visited rooms list.




Software Engineer. Find me @

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Let’s be full stack!

Number of Steps to Reduce a Number to Zero — Day 74(Python)

OpenStack & CORE Application

pasted image 0 (3)

DevOps Is Not A Culture, Not Yet.

Jupyter Notebook — Revolutionizing The Coding Environment

👋 Awesome Hunt — PART 2 — Case of the zoomies

Homelab Revisited: Processors

CRUD Application with Deno

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @

More from Medium

CaDS— Code and Data Society

Singleton pattern in python libraries

Changing POSIX code to Python

What is Python Automation?