{x}
blog image

Minimize Malware Spread

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

Some nodes initial are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network after the spread of malware stops. We will remove exactly one node from initial.

Return the node that, if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.

Note that if a node was removed from the initial list of infected nodes, it might still be infected later due to the malware spread.

 

Example 1:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

Example 2:

Input: graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0

Example 3:

Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
Output: 1

 

Constraints:

  • n == graph.length
  • n == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] is 0 or 1.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length <= n
  • 0 <= initial[i] <= n - 1
  • All the integers in initial are unique.

Solution Explanation: Minimize Malware Spread

This problem asks to find the node in the initial set that, if removed, would minimize the spread of malware in a network represented by an adjacency matrix. The solution employs a Union-Find algorithm for efficient determination of connected components.

Approach:

  1. Union-Find Initialization: A Union-Find data structure is created to represent the connected components of the network. Each node initially represents its own component.

  2. Building Connected Components: The adjacency matrix graph is iterated. If graph[i][j] == 1, indicating a connection between nodes i and j, the union() operation in the Union-Find structure merges their components. After this step, each connected component is identified by its root node.

  3. Counting Infected Nodes per Component: A counter (cnt in the code) is used to track the number of initially infected nodes (initial array) in each connected component. For each node in initial, its root node (representing its component) is identified using the find() operation from the Union-Find structure and its count in cnt is incremented.

  4. Iterating through Initial Infected Nodes: The code iterates through each node x in the initial array. For each node:

    • It finds the root of its connected component using find(x).
    • If the number of infected nodes in that component (cnt[root]) is 1, it means removing x would isolate that infection.
    • The size of the component (sz obtained using getSize(root) from Union-Find) is then compared against a running maximum (mx).
    • If sz is greater than mx, or if sz equals mx but x has a smaller index than the current minimum (ans), x becomes the new candidate node to remove (ans).

  5. Handling Multiple Infections in a Component: If after the loop, ans hasn't changed (meaning no single-infected component was found), it means all components have multiple infections. In this case, the node with the smallest index from initial is returned.

Time Complexity:

  • Union-Find initialization: O(n) where n is the number of nodes.
  • Building connected components: O(n^2) due to iterating through the adjacency matrix. The union() operation in Union-Find is amortized O(1).
  • Counting infected nodes: O(k), where k is the number of initially infected nodes (which is less than or equal to n). The find() operation is amortized O(1).
  • Iterating and comparing components: O(k). getSize() and find() are again amortized O(1).

Therefore, the overall time complexity is dominated by building connected components, making it O(n^2).

Space Complexity:

  • Union-Find data structure: O(n) to store parent pointers and component sizes.
  • Counter cnt: O(n) in the worst case (if all nodes are in separate components).

Thus, the overall space complexity is O(n).

Code Example (Python):

class UnionFind:
    # ... (Union-Find implementation as shown in the previous response) ...
 
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        # ... (rest of the solution as shown in the previous response) ...

The other language examples (Java, C++, Go, TypeScript) follow the same algorithm, differing only in syntax and data structure implementation. The core Union-Find logic remains consistent across all versions.