0841 - Keys and Rooms (Medium)

Problem Link

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

Problem Statement

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.

Example 1:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

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.

Approach 1: DFS

We can use DFS to traverse from the first room and mark every room that we could visit. At the end, we check if all rooms have been visited or not.

C++

Written by @wingkwong

class Solution {
public:
    void dfs(vector<vector<int>>& rooms, int i, vector<int>& vis) {
        // mark the room i visited
        vis[i] = 1;
        // for each room we can go from the current room
        for(auto r : rooms[i]) {
            // if it is not visited
            if(!vis[r]) {
                // we go to that room
                dfs(rooms, r, vis);
            }
        }
    }
    
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = (int) rooms.size();
        vector<int> vis(n, 0);
        dfs(rooms, 0, vis);
        int ok = 1;
        for(int i = 0; i < n; i++) ok &= vis[i];
        return ok;
    }
};

Rust

Written by @wingkwong

impl Solution {
    fn dfs(i: usize, vis: &mut Vec<bool>, rooms: &Vec<Vec<i32>>) {
        vis[i] = true;
        for next in rooms[i].iter().map(|&next| next as usize) {
            if !vis[next] {
                Self::dfs(next, vis, rooms);
            }
        }
    }
    
    pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
        let mut vis = vec![false; rooms.len()];
        Self::dfs(0, &mut vis, &rooms);
        vis.iter().all(|&x| x)
    }
}

JavaScript

Written by @radojicic23

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let visited = new Set();
    dfs(0);
    return visited.size == rooms.length;
    
    function dfs(room) {
        if (!visited.has(room)) {
            visited.add(room);
            for (i of rooms[room]) {
                dfs(i);
            }
        }
    }
};

Python

Written by @radojicic23

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set()
        def dfs(room):
            if room not in visited:
                visited.add(room)
                for i in rooms[room]:
                    dfs(i)
        dfs(0)
        return len(rooms) == len(visited)