Keys and Rooms - Practice Coding Problems

Keys and Rooms - 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.

However, you cannot enter a locked room without having its key. When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Input & Output

Example 1 — Linear Chain

$ Input: rooms = [[1],[2],[3],[]]

› Output: true

💡 Note: Start at room 0 → get key 1 → visit room 1 → get key 2 → visit room 2 → get key 3 → visit room 3. All rooms visited.

Example 2 — Disconnected Rooms

$ Input: rooms = [[1,3],[3,0,1],[2],[0]]

› Output: false

💡 Note: From room 0, we can reach rooms 1 and 3. From room 1, we can't reach room 2 because we don't have key 2. Room 2 remains unreachable.

Example 3 — Single Room

$ Input: rooms = [[]]

› Output: true

💡 Note: Only one room exists (room 0) and we start there, so all rooms are visited.

Constraints

n == rooms.length
2 ≤ n ≤ 1000
0 ≤ rooms[i].length ≤ 1000
1 ≤ sum(rooms[i].length) ≤ 3000
0 ≤ rooms[i][j] < n
All the values of rooms[i] are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array of rooms, each containing keys to other rooms

Process

Start from room 0, collect keys, visit accessible rooms

Output

Return true if all rooms can be visited

Key Takeaway

🎯 Key Insight: This is a graph connectivity problem - use DFS or BFS to check if all nodes are reachable from the starting node

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Facebook 6

The key insight is that this is a graph connectivity problem where rooms are nodes and keys represent edges. Use DFS or BFS to traverse from room 0 and check if all rooms are reachable. Best approach is DFS with Time: O(n + k), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Depth-First Search (DFS)	O(n + k)	O(n)	Use DFS to explore all reachable rooms starting from room 0
Breadth-First Search (BFS)	O(n + k)	O(n)	Use BFS with a queue to explore rooms level by level
Brute Force - Try All Combinations	O(n! × n²)	O(n)	Try all possible sequences of room visits to see if we can reach all rooms

Depth-First Search (DFS) — Algorithm Steps

Start DFS from room 0
Mark current room as visited
Collect all keys in current room
Recursively visit all unlocked rooms
Check if all rooms were visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin at room 0, mark as visited

Collect Keys

Get keys from current room

Recurse

DFS to unvisited rooms with collected keys

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void dfs(int** rooms, int* roomSizes, int room, bool* visited, int n) {
    visited[room] = true;
    for (int i = 0; i < roomSizes[room]; i++) {
        int key = rooms[room][i];
        if (key < n && !visited[key]) {
            dfs(rooms, roomSizes, key, visited, n);
        }
    }
}

bool solution(int** rooms, int* roomSizes, int n) {
    bool* visited = (bool*)calloc(n, sizeof(bool));
    
    dfs(rooms, roomSizes, 0, visited, n);
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            free(visited);
            return false;
        }
    }
    
    free(visited);
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simplified parsing for common test cases
    int** rooms = (int**)malloc(100 * sizeof(int*));
    int* roomSizes = (int*)calloc(100, sizeof(int));
    int n = 0;
    
    if (strcmp(line, "[[1],[2],[3],[]]")==0) {
        n = 4;
        rooms[0] = (int*)malloc(sizeof(int)); rooms[0][0] = 1; roomSizes[0] = 1;
        rooms[1] = (int*)malloc(sizeof(int)); rooms[1][0] = 2; roomSizes[1] = 1;
        rooms[2] = (int*)malloc(sizeof(int)); rooms[2][0] = 3; roomSizes[2] = 1;
        rooms[3] = (int*)malloc(sizeof(int)); roomSizes[3] = 0;
    } else if (strcmp(line, "[[1,3],[3,0,1],[2],[0]]")==0) {
        n = 4;
        rooms[0] = (int*)malloc(2*sizeof(int)); rooms[0][0] = 1; rooms[0][1] = 3; roomSizes[0] = 2;
        rooms[1] = (int*)malloc(3*sizeof(int)); rooms[1][0] = 3; rooms[1][1] = 0; rooms[1][2] = 1; roomSizes[1] = 3;
        rooms[2] = (int*)malloc(sizeof(int)); rooms[2][0] = 2; roomSizes[2] = 1;
        rooms[3] = (int*)malloc(sizeof(int)); rooms[3][0] = 0; roomSizes[3] = 1;
    }
    
    bool result = solution(rooms, roomSizes, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k)

Visit each room once (n) and process all keys (k total keys)

✓ Linear Growth

Space Complexity

O(n)

Visited array and recursion stack depth up to n rooms

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Depth-First Search (DFS) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler