Leetcode question (Asked in Google interview), but with some my own modification

help
1

There is this leetcode question, asked once in google interview…
link- - LeetCode

What is the best approach to solve the modified version of this problem…
Modified version-:

There are N rooms and you start from any room . 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 are locked .

You have a master key, which can open any room you want, Your task is to count the minimum number of times master key is used…

You can walk back and forth between rooms freely.

return the Minimum number of time master key is used.

1 Like
2

Create a directed graph with N nodes. Connect all room specific nodes to other rooms for which this room has a key with weight 0. Then you just need to find the minimum number of edges you need to add to get a strongly connected graph.

1 Like