924. Minimize Malware Spread

Problem Description

In this problem, we are given a network of n nodes where connections between the nodes are represented by an n x n adjacency matrix called [graph](/problems/graph_intro). In this matrix, if graph[i][j] == 1, then node i is directly connected to node j. Some of these nodes are initially infected with malware (given in the array initial). The malware spreads between directly connected nodes as long as at least one of the nodes has the malware. This spread continues until it cannot be passed along any further between nodes.

Our goal is to identify one node that we can remove from the initially infected list to minimize the total number of nodes that will be infected after the malware has stopped spreading. The function should return the smallest-indexed node that would result in the minimum number of infections.

It's important to note that removing a node from the initially infected list doesn't guarantee that it will not become infected later due to the malware's spread.

Intuition

To solve this problem, the code takes a union-find approach to determine which nodes are connected in a group, and to gather information about the size of each connected component within the graph. The algorithm works through the following steps:

1. Initialize each node's parent to itself, creating n separate sets, and set the initial size of each set to 1.
2. Loop through the adjacency matrix [graph](/problems/graph_intro) and perform a union of each pair of directly connected nodes (graph[i][j] == 1). This is done by finding the root parents of both nodes and setting one as the parent of the other, effectively joining the sets. The size array is updated to reflect the new size of the combined set.
3. Iterate over the initially infected nodes after sorting them. This ensures that if multiple nodes can be removed to achieve the same minimized infection result, we will return the one with the smallest index.
4. For each initially infected node, temporarily exclude it and tally the total infections that would result by adding the sizes of the unique parent sets containing the other initially infected nodes.
5. If this tally is smaller than the current minimum number of infections, update the minimum and set the result to the current node.

By executing these steps, the algorithm finds the node which, when removed, would lead to the smallest number of infected nodes. In cases where multiple nodes could be chosen, it opts for the one with the smallest index.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution uses the union-find algorithm to group connected nodes and dynamically track the size of these groups. Union-find is a data structure that provides efficient operations to find the root of an element (indicating which group it belongs to) and to unify two elements if they are in different sets (or groups). Here is a detailed walk-through of its implementation in the given solution:

Union-Find Data Structure

• A parent array p is initialized, where p[i] represents the parent of node i. Initially, each node is its own parent.
• A size array is initialized, where size[i] represents the size of the tree for which node i is the root. Initially, each node is in a separate group of size 1.

Union Operation

• Two loops iterate over the rows and columns of the adjacency matrix representing the graph.
• If graph[i][j] == 1, nodes i and j are directly connected and should be considered part of the same group.
• We use a find function to get the root parent for nodes i and j, which effectively finds which groups they belong to.
• If they have the same root parent, they are already in the same group, and no action is taken.
• Otherwise, they belong to different groups, and a union is performed by updating the parent of one root to the other. The size of the new root's group is incremented by the size of the merged group's size.

Find Operation

• To determine which node is the parent (or root) of a given node, and thus which group it belongs to, we use the find function.
• The find function will recursively update the node's parent to its root by path compression, which flattens the structure of the tree and speeds up subsequent find operations.

Identifying the Critical Node

• The array of initially infected nodes initial is sorted to ensure the smallest index is prioritized if there are multiple candidates.
• A loop iterates over the sorted initial array to consider the removal of each node.
• Inside this loop, a set s is created to store unique root parents associated with the remaining initially infected nodes.
• A temporary count t is used to tally the total possible infections without the considered node.
• A nested loop iterates through the initial array again to count infections caused by the remaining initially infected nodes.
• If the root of the current node is not already in the set s (to avoid double counting), the size of the group with that root is added to t (since removing a node from initial doesn't prevent it from being infected by others).
• If the tally t is less than the current minimum mi, we update mi to the new lower count and set res to the index of the node considered for removal.
• The loop continues until all initially infected nodes are considered, ensuring that the one leading to the smallest M(initial) is found.

Conclusion

By leveraging the union-find algorithm with path compression, we can efficiently identify the node that minimizes the spread of malware after exclusion and ensure we return the smallest index in the case of ties.

Example Walkthrough

Let's say we have a network of 4 nodes, represented by the adjacency matrix graph below:

1graph = [
2  [1, 1, 0, 0],
3  [1, 1, 1, 0],
4  [0, 1, 1, 0],
5  [0, 0, 0, 1]
6]

And we have an array initial showing which nodes are initially infected with malware:

1initial = [1, 3]

We can walk through the solution approach as follows:

1. Union-Find Initialization: We start by initializing the parent and size arrays.

   • parent would be [0, 1, 2, 3]
   • size would be [1, 1, 1, 1]

2. Union Operations: Next, we examine the adjacency matrix and perform union operations.

   • For graph[0][1], nodes 0 and 1 are connected, so we unite them, which leads to:
     • parent being updated to [0, 0, 2, 3]
     • size being updated to [2, 1, 1, 1] because the size of the group with root 0 now includes node 1.
   • For graph[1][2], nodes 1 and 2 are connected, and indirectly node 0 is also connected to node 2, so we unite them under root 0:
     • parent being updated to [0, 0, 0, 3]
     • size being updated to [3, 1, 1, 1]
   • graph[3] has no connections thus no union operations are needed.

3. Sorting Initially Infected Nodes: We ensure that initial is sorted to consider the smallest index first:

   • Sorted initial would be [1, 3]

4. Identifying the Critical Node: We start with the first node in initial and imagine removing it.

   • Considering node 1 for removal, we find that:
     • Node 3 is in its own group and will only infect itself.
     • There are no other initially infected nodes connected to node 1, as we temporarily exclude it.
   • The total number of infections in this case would be 1 (from node 3).
   • Next, considering node 3 for removal:
     • Now nodes 0, 1, and 2 are connected and since node 1 is infected, all three will get infected.
     • The total would then be 3.
   • Comparing the two removals, we find that excluding node 1 leads to fewer infections.

5. Result: From this process, we find that removing node 1 from initial leads to the minimum number of infections. The final answer is 1, as it is the smallest-indexed node that minimizes the spread of malware.

In this simple network, the algorithm efficiently finds that removing node 1, despite it potentially getting infected through other paths, leads to the lowest number of total infected nodes.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several nested loops and the union-find operations.

1. The outer loop for merging nodes of the graph runs n times, where n is the number of nodes in the graph.
2. The inner loop for checking all possible pairs runs (n-1) + (n-2) + ... + 1 times, which simplifies to O(n^2) when summing the arithmetic series.
3. The find function, which is called within these loops, has an almost constant time complexity due to path compression. The worst-case scenario for each call can be assumed to be O(log n), but because of path compression, it tends to be much closer to O(1) over many calls.
4. The last loop iterates over the initial infected nodes, which let's say there are k infected nodes. It calls the find function and sums the sizes of connected components, which could be O(n) in a sparse graph but is usually much less if infected nodes are clustered.

Considering these points, the time complexity can be estimated as follows:

• Union-find operations + loop through all pairs of nodes: O(n^2 * \alpha(n)), where \alpha is the Inverse Ackermann function, which is a very slowly growing function and for all practical purposes can be considered constant, thus reducing this to O(n^2).
• Loop through initial nodes and associated operations: O(k * n), where k is the number of initial infected nodes.

The final time complexity is O(n^2 + k * n), but because k <= n, this simplifies to O(n^2).

Space Complexity

The space complexity of the code is determined by the storage for the parent and size array, the set s, and any overhead needed for the union-find data structure.

1. The parent array p uses O(n) space.
2. The size array also uses O(n) space.
3. The set s in the worst case might store k elements where k is the number of initial infected nodes.

Thus, the space complexity is O(n + k), which in the worst case simplifies to O(n) if every node is an initially infected node.

Learn more about how to find time and space complexity quickly using problem constraints.