Leetcode: Minimize Malware Speed

This question is asked at ByteDance, Bloomberg, and Dropbox. 

You are given a network of n nodes represented as an n x n adjacency matrix, denoted as graph, where the ith node is directly connected to the jth node if graph[i][j] == 1. 

Some nodes are initially affected by the malware and when 2 nodes are directly connected and at least one of the 2 nodes are infected, then most nodes will be affected by the malware. 

Suppose M(initial) is the final number of nodes infected with malware after the spread stops, and we remove exactly one node from the initial. 

We want to minimize M(initial) the number of nodes that are spread. 

Let's draw the graph for [[1,0,0],[0,1,0],[0,0,1]].

Let's reframe the problem to corona virus. 

In a cycle red is infected and we can only fix one "patient" at a time so not possible to save a nation. In other areas, we can fix one infected patient and save a nation in this manner. 

The pseudocode explanation is below: 

The first step is to apply union find so that I can get the number of components with size of each component. Iterate through every infected patient and try to find the number of patients in each country. Country with only one patient will be save first and countries having one patient with same population having a small index will be saved first. 

So union find all nodes.

Count the union size of each union set, and cut the malware number of each set.

Return the biggest union malware if there is only one malware. If no such union has only one malware, return the malware with the minimum index. The time complexity is O(N^2). Return malware with minimum index if no such union that has only one malware. 

Here's another way to understand the logic:

1. Form groups containing nodes reachable from one another

2. Store the size of each group in a vector

3. Store number of initially infected nodes present for group.

Nodes in the biggest group such that it is the only initially infected node of the group would remove the most node from getting infected. If multiple nodes like this, remove the one with the lowest value. 

Here's the code:

//graph representation  

private int[] p;

public int minMalwareSpread (int[][] g, int[] initial) {

    int n = g.length; 

    p = new int [n];

    //beginning of union find. Set each beginning node to itself. 

    for(int i = 0; i < n; i++) {

        p[i] = i;

    }

    //union all the nodes together, setting j to be the parent of i. 

    for(int i = 0; i < n; i++) {

        for(int j = i + 1; j < n; j++) {

            if(g[i][j] == 1) {

                union(i, j); 

            }

        }

        int[] ufSize = new int[n];

        int[] malCount = new int[n];

        //get the graph size of the parent

        for(int i = 0; i < n; i++) {

            ufSize[find(i)]++; 

        }

        //add the malware count and add one. 

        for(int i = 0; i < initial.length; i++) {

            malCount[find(init)]++; 

        }

        int res = -1;

        int maxSize = 0; 

        //sort the initial array in order. 

        Arrays.sort(initial);

        for(int init : initial) {

            int idx = find(init); 

            if(malCount[idx] == 1 && ufSize[idx] > maxSize) {

                //see the union find size and find the maximum union find size. 

                maxSize = ufSize[idx]; 

                res = init; 

            }

        }

    //return the result if there is a maximum sizer. 

    if(maxSize != 0) return res;

    //return the initial element otherwise (least element)

    else return initial[0];         

    }

    

    private void union(int i, int j) {

        //union these 2 by setting the parent of i to j. 

        p[find[i]] = find[j];

    }

    private int find(int i) {

        //find the parent of a particular element 

        if(p[i] == i) {

            return i;

        } else {

            p[i] = find(p[i]);

            return p[i]; 

        }

    }

}