924. Minimize Malware Spread Explanation and Solution | 踏不遍青山

924. Minimize Malware Spread Explanation and Solution | 踏不遍青山

LeetCode Link 924. Minimize Malware Spread

The problem statement is a little bit to follow. Actually, the task is:

1. Firstly, calculate the size of each connected set
2. Secondly, two conditions:

• If there are many sets only have one infected node, then return the set which has the maximum size.
• If there are no sets that only have one infected node, then return the minimum index infected node.

Explanation

As stated before, we can solve this problem by using disjoint set data structures, which have union and find methods. Why? Because we have to know the connections of the nodes. If there are two or more nodes infected and they are all connected, even if we remove it, it will not make any difference. So, we should spread these nodes into disjoint sets and a little difference from the common disjoint sets is that we should know the size of each sets. Do not forget to initialize the roots array and the counts array, as each set initially has 1 node and each node is his own root.

Ok, then, we use a HashMap to save the infected nodes in each set. How? We iterate the initial array, and to each infected node, we find its root, and make the recorded infected ++. In this way, we can know how many nodes are infected in each set.

We have to sort the initial array, the reason is that if we do not have any sets with only 1 infected node, we should return the infected with minimum index.

The last step is we iterate the initial array again. We should keep three varibles, the first one is the final result, the second one is the size of the set of the current infected node belong to, the last one is the maximum set size.
This time, we check if there is only one infected node in the set, if is, we compare the current set size with the global maximum size, if the set size is larger than the maximum size, the result is the current node; otherwise, simply return the first infected node.

Read full article from 924. Minimize Malware Spread Explanation and Solution | 踏不遍青山