Keys And Rooms Leetcode Solution

Welcome back to the Leetcode daily series. We have a very interesting problem ahead of us today so get your thinking caps on!

Understanding The Problem

Take a look at the problem described below.

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.

This is not a typical problem, the description uses an analogy to distract you from the core concept required to solve this problem.

Try to figure out which concept is being abstracted to a vague problem here.

Intuition

If we think of each "room" as a node in a graph, and each "key" as an edge between two rooms, this problem reduces to finding out if there is a path that covers all nodes of the graph, starting from node 0. In this case, all the keys that are found in a room, are essentially the neighbors for that room/node.

Let's see the following example to make this analogy clear.

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.

The graph for this particular input would look something like this.

That's all there is to this problem! A regular DFS traversal would be sufficient for us to solve it.

Depth-first search (DFS) is an algorithm for traversing a graph or tree data structure. It involves searching through the nodes of the graph by following each path as far as it will go before backtracking and trying a different path. We'll be using recursion to implement this algorithm.

Here are the high-level steps we'll need to follow:

1. Visit the starting node.

2. Recursively visit all of its unvisited neighbors.

3. If all of the neighbors have been visited, backtrack to the previous node and visit one of its other unvisited neighbors.

4. Repeat this process until all nodes have been visited.

If you need an in-depth refresher on DFS, check out the additional links at the end of this article.

Coding Up The Steps

Here's the full solution to this problem.

class Solution {
public:
    void helper(vector<vector<int>>& rooms,vector<bool> &visited,int pos){
        visited[pos] = true;

        for(int i = 0;i < rooms[pos].size(); i++){
            if(!visited[rooms[pos][i]])
                helper(rooms,visited,rooms[pos][i]);
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<bool> visited(n,false);

        helper(rooms,visited,0);
        for(bool i : visited){
            if(!i) return false;
        }
        return true;
    }
};

The only additional step after DFS that we have to perform is to check whether all the nodes have been visited or not after the entire DFS traversal.

That's it for today! Do subscribe to my newsletter if you'd like these solutions to come to your email directly.

Cheers!

Additional Resources

• Depth First Search: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/