Leetcode - Keys and Rooms Solution — The Poor Coder

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Text

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start 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 go to every room, we return true.

Example 2:

Text

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

Solution in Python#

Python

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        rooms_already_checked = set()
        rooms_to_check = set({0})

        while rooms_to_check:
            rooms_to_check_temp = set()
            for i in rooms_to_check-rooms_already_checked:
                rooms_to_check_temp.update(rooms[i])
                rooms_already_checked.add(i)
            rooms_to_check = rooms_to_check_temp
        return len(rooms_already_checked)==len(rooms)

Apr 242021

Leetcode - Accounts Merge Solution

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would…

leetcode Depth-first-search Union Find4 min read

Mar 202021

Leetcode - Letter Combinations of a Phone Number Solution

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone…

leetcode string backtracking1 min read

May 112021

Leetcode - Camelcase Matching Solution

A query word matches a given pattern if we can insert lowercase letters to the pattern word so that it equals the query. (We may insert each character at any position, and may insert 0 characters.) Given a list of…

leetcode string trie2 min read

Solution in Python#

Related posts

Leetcode - Accounts Merge Solution

Leetcode - Letter Combinations of a Phone Number Solution

Leetcode - Camelcase Matching Solution