Keys and Rooms - LeetCode75 Python Solution Explained

The Keys and Rooms problem (LeetCode75) is a popular graph traversal challenge that tests your understanding of DFS/BFS, recursion, and set-based tracking. It is commonly asked in technical interviews because it evaluates problem-solving skills in graph exploration and reachability.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given n rooms labeled 0 to n-1. Each room may contain keys to other rooms. Initially, you are in room 0. You can only enter a room if you have its key.

Return True if you can visit all rooms, otherwise return False.

rooms[i] is a list of keys in room i.
Each key is an integer representing another room.

Example 1

Input:

rooms = [[1],[2],[3],[]]

Output:

True

Explanation:

Start in room 0 → get key 1
Room 1 → get key 2
Room 2 → get key 3
Room 3 → no keys
All rooms visited → return True

Example 2

Input:

rooms = [[1,3],[3,0,1],[2],[0]]

Output:

False

Explanation:

Cannot visit room 2 from room 0 → return False

Complete Python Solution

from typing import List

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        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) == n

Step-by-Step Explanation

Step 1: Initialize Tracking

Create a visited set to track rooms you have entered.

visited = set()

Step 2: Define DFS Function

Use DFS to explore rooms recursively:

def dfs(room):
    if room in visited:
        return
    visited.add(room)
    for key in rooms[room]:
        dfs(key)

If a room is already visited → skip.
Otherwise, mark it visited.
Recursively visit all rooms for which you have keys.

Step 3: Start DFS from Room 0

dfs(0)

Step 4: Check if All Rooms Are Visited

return len(visited) == n

If the number of visited rooms equals total rooms → return True.
Otherwise → False.

Time and Space Complexity

Time Complexity:O(N + E)
- N = number of rooms
- E = total number of keys across all rooms
- Each room and key is visited once
Space Complexity:O(N)
- visited set stores up to N rooms
- Recursion stack can go up to N depth

Edge Cases

Single room: rooms = [[]] → return True.
No keys in any room except room 0: check if DFS reaches all rooms.
Duplicate keys: handled by visited set.
Disconnected rooms: return False.

Real-World Applications

Access Control Systems: Ensuring users can access all permitted areas.
Game Level Design: Check if all game rooms are reachable.
Network Connectivity: Verifying that all nodes in a network can be visited.
Resource Allocation: Ensuring all dependent resources are reachable from the start point.

Conclusion

The Keys and Rooms problem is a great exercise in graph traversal using DFS, recursion, and set-based tracking. By marking rooms as visited and recursively exploring accessible rooms, we can efficiently determine whether all rooms are reachable.

This problem strengthens your understanding of:

Recursive DFS traversal
Handling cycles using a visited set
Reachability in graph-like structures

It is highly valuable for technical interviews and practical applications in security systems, games, and network connectivity.

Keys and Rooms – LeetCode75 Python Solution Explained