algoadvance

Leetcode 841. Keys and Rooms

Problem Statement

There are n rooms in a building, numbered from 0 to n-1. Each room might have some keys to access other rooms. Initially, only room 0 is unlocked. You are given an array rooms where rooms[i] is a list of keys in the i-th room. A key rooms[i][j] = v allows you to open room v.

You need to determine if you can visit all the rooms starting from room 0.

The problem can be summarized as:

Example:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We begin 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 visit every room, we return true.

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: 
We can't access room 2 from the given keys.

Clarifying Questions

  1. Can a room have multiple keys to the same room?
    • Yes, a room can contain duplicate keys, though it will not affect the final outcome.
  2. Can there be empty rooms?
    • Yes, some rooms may not contain any keys.
  3. Maximum value of n?
    • Typically, the constraints on n should be provided. Let’s assume n can be up to 10^4.
  4. What if rooms array is empty?
    • If rooms array is empty, the function should return false since there are no rooms to visit.

Strategy

  1. Graph Representation:
    • Think of each room as a node in a graph. An edge exists between two nodes if there is a key to the second room in the first room.
  2. Graph Traversal:
    • Perform a graph traversal (either DFS or BFS) starting from room 0.
    • Use a set or an array to keep track of the rooms we have visited.
  3. Goal:
    • Traverse all rooms and see if we can visit each room at least once.

Code

Here’s the implementation using Depth-First Search (DFS):

#include <vector>
#include <stack>
#include <unordered_set>

class Solution {
public:
    bool canVisitAllRooms(std::vector<std::vector<int>>& rooms) {
        int n = rooms.size();
        std::vector<bool> visited(n, false);
        std::stack<int> stack;
        
        stack.push(0);
        visited[0] = true;
        
        while (!stack.empty()) {
            int room = stack.top();
            stack.pop();
            
            for (int key : rooms[room]) {
                if (!visited[key]) {
                    visited[key] = true;
                    stack.push(key);
                }
            }
        }
        
        for (bool v : visited) {
            if (!v) return false;
        }
        
        return true;
    }
};

Strategy

  1. Initialization:
    • Start with room 0. Use a stack for DFS traversal.
    • Use a visited array to mark rooms that have been visited.
  2. Traversal:
    • Push room 0 onto the stack and mark it as visited.
    • While the stack is not empty, pop the top element (the current room).
    • For each key in the current room:
      • If the corresponding room has not been visited, mark it as visited and push it onto the stack.
  3. Check Visit Completion:
    • After traversal, check if all rooms have been visited.

Time Complexity

This approach ensures we properly check if all rooms can be visited starting from room 0.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI