Skip to content

841. Keys and Rooms

DifficultyMedium

Description

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.

Solutions

Solution 1: Depth-First Search (DFS)

Thinking

Rooms form a directed graph whose edges are keys. We ask whether \(0\) reaches every room. \(n\le 1000\), so one traversal is enough.

DFS from \(0\) follows keys; success is \(|\textit{vis}|=n\).

We can use the Depth-First Search (DFS) method to traverse the entire graph, count the number of reachable nodes, and use an array vis to mark whether the current node has been visited to prevent repeated visits.

Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, there are nodes that cannot be reached.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes, and \(m\) is the number of edges.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(i: int):
            if i in vis:
                return
            vis.add(i)
            for j in rooms[i]:
                dfs(j)

        vis = set()
        dfs(0)
        return len(vis) == len(rooms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private int cnt;
    private boolean[] vis;
    private List<List<Integer>> g;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        g = rooms;
        vis = new boolean[g.size()];
        dfs(0);
        return cnt == g.size();
    }

    private void dfs(int i) {
        if (vis[i]) {
            return;
        }
        vis[i] = true;
        ++cnt;
        for (int j : g.get(i)) {
            dfs(j);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        int cnt = 0;
        bool vis[n];
        memset(vis, false, sizeof(vis));
        function<void(int)> dfs = [&](int i) {
            if (vis[i]) {
                return;
            }
            vis[i] = true;
            ++cnt;
            for (int j : rooms[i]) {
                dfs(j);
            }
        };
        dfs(0);
        return cnt == n;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func canVisitAllRooms(rooms [][]int) bool {
    n := len(rooms)
    cnt := 0
    vis := make([]bool, n)
    var dfs func(int)
    dfs = func(i int) {
        if vis[i] {
            return
        }
        vis[i] = true
        cnt++
        for _, j := range rooms[i] {
            dfs(j)
        }
    }
    dfs(0)
    return cnt == n
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function canVisitAllRooms(rooms: number[][]): boolean {
    const n = rooms.length;
    const vis: boolean[] = Array(n).fill(false);
    const dfs = (i: number) => {
        if (vis[i]) {
            return;
        }
        vis[i] = true;
        for (const j of rooms[i]) {
            dfs(j);
        }
    };
    dfs(0);
    return vis.every(v => v);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
        let n = rooms.len();
        let mut is_open = vec![false; n];
        let mut keys = vec![0];
        while !keys.is_empty() {
            let i = keys.pop().unwrap();
            if is_open[i] {
                continue;
            }
            is_open[i] = true;
            rooms[i].iter().for_each(|&key| keys.push(key as usize));
        }
        is_open.iter().all(|&v| v)
    }
}

Solution 2: BFS

Thinking

Solution 1 follows keys with an explicit stack. The same reachability is a queue: start at \(0\) and enqueue a room when a key to it is found and that room is still unvisited. The visited marks still drop duplicate keys, and the answer still compares the visited count with \(n\).

We can also use the Breadth-First Search (BFS) method to traverse the entire graph. We use a hash table or an array vis to mark whether the current node has been visited to prevent repeated visits.

Specifically, we define a queue \(q\), initially put node \(0\) into the queue, and then continuously traverse the queue. Each time we take out the front node \(i\) of the queue, if \(i\) has been visited, we skip it directly; otherwise, we mark it as visited, and then add the nodes that \(i\) can reach to the queue.

Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, it means that there are unreachable nodes.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n)\). Where \(n\) is the number of nodes, and \(m\) is the number of edges.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        vis = set()
        q = deque([0])
        while q:
            i = q.popleft()
            if i in vis:
                continue
            vis.add(i)
            q.extend(j for j in rooms[i])
        return len(vis) == len(rooms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] vis = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int cnt = 0;
        while (!q.isEmpty()) {
            int i = q.poll();
            if (vis[i]) {
                continue;
            }
            vis[i] = true;
            ++cnt;
            for (int j : rooms.get(i)) {
                q.offer(j);
            }
        }
        return cnt == n;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<bool> vis(n);
        queue<int> q{{0}};
        int cnt = 0;
        while (q.size()) {
            int i = q.front();
            q.pop();
            if (vis[i]) {
                continue;
            }
            vis[i] = true;
            ++cnt;
            for (int j : rooms[i]) {
                q.push(j);
            }
        }
        return cnt == n;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func canVisitAllRooms(rooms [][]int) bool {
    n := len(rooms)
    vis := make([]bool, n)
    cnt := 0
    q := []int{0}
    for len(q) > 0 {
        i := q[0]
        q = q[1:]
        if vis[i] {
            continue
        }
        vis[i] = true
        cnt++
        for _, j := range rooms[i] {
            q = append(q, j)
        }
    }
    return cnt == n
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function canVisitAllRooms(rooms: number[][]): boolean {
    const vis = new Set<number>();
    const q: number[] = [0];

    while (q.length) {
        const i = q.pop()!;
        if (vis.has(i)) {
            continue;
        }
        vis.add(i);
        q.push(...rooms[i]);
    }

    return vis.size == rooms.length;
}

Solution 3: Explicit Stack

Thinking

Rooms form a directed graph whose edges are keys. The question is whether room \(0\) reaches every room. With \(n \le 1000\), one traversal is enough. Following a chain of keys by recursion uses a call depth equal to the room count and overflows Python once the chain reaches length \(1000\). A stack therefore holds the rooms still to open: a popped room is skipped when it was already visited, and otherwise it is marked and its keys are pushed. Duplicate keys may push the same room again, and the mark expands it only once. Every room is reachable when the visited count equals \(n\).

Start at room \(0\) and walk the reachable rooms with an explicit stack. The stack begins with \(0\). When room \(i\) is popped, skip it if it has already been visited; otherwise mark it and push the room behind each key found in \(i\). A repeated key only pushes that room again, and the later pop is skipped.

Finally, check whether every room was visited. If so, return true; otherwise some room cannot be reached.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes, and \(m\) is the number of edges.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        vis = [False] * n
        stk = [0]
        while stk:
            i = stk.pop()
            if vis[i]:
                continue
            vis[i] = True
            for j in rooms[i]:
                stk.append(j)
        return all(vis)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] vis = new boolean[n];
        Deque<Integer> stk = new ArrayDeque<>();
        stk.push(0);
        while (!stk.isEmpty()) {
            int i = stk.pop();
            if (vis[i]) {
                continue;
            }
            vis[i] = true;
            for (int j : rooms.get(i)) {
                stk.push(j);
            }
        }
        for (boolean v : vis) {
            if (!v) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<char> vis(n);
        vector<int> stk = {0};
        while (!stk.empty()) {
            int i = stk.back();
            stk.pop_back();
            if (vis[i]) {
                continue;
            }
            vis[i] = 1;
            for (int j : rooms[i]) {
                stk.push_back(j);
            }
        }
        for (char v : vis) {
            if (!v) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func canVisitAllRooms(rooms [][]int) bool {
    n := len(rooms)
    vis := make([]bool, n)
    stk := []int{0}
    for len(stk) > 0 {
        i := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if vis[i] {
            continue
        }
        vis[i] = true
        for _, j := range rooms[i] {
            stk = append(stk, j)
        }
    }
    for _, v := range vis {
        if !v {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function canVisitAllRooms(rooms: number[][]): boolean {
    const n = rooms.length;
    const vis: boolean[] = Array(n).fill(false);
    const stk: number[] = [0];
    while (stk.length) {
        const i = stk.pop()!;
        if (vis[i]) {
            continue;
        }
        vis[i] = true;
        for (const j of rooms[i]) {
            stk.push(j);
        }
    }
    return vis.every(v => v);
}

Comments