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.lengthn == graph[i].length2 <= n <= 300graph[i][j] is 0 or 1.graph[i][j] == graph[j][i]graph[i][i] == 11 <= initial.length <= n0 <= initial[i] <= n - 1initial are unique.Problem Overview: You are given an undirected graph represented by an adjacency matrix where some nodes are initially infected with malware. Removing exactly one infected node can stop the spread from that source. The goal is to remove the node that minimizes the total number of infected nodes after the malware spreads through connected components. If multiple choices produce the same result, return the smallest node index.
Approach 1: Union-Find to Segment Components (O(n^2) time, O(n) space)
Treat the graph as a set of connected components. Use a Union Find structure to merge nodes whenever graph[i][j] == 1. After building components, compute the size of each component and count how many initially infected nodes fall inside each component. If a component contains exactly one infected node, removing that node prevents the entire component from being infected. Iterate through the initial list and pick the node whose component has a single infection and the largest component size. If no such component exists, return the smallest index from the initial list. This approach works well because malware spreads only within connected components.
Approach 2: DFS/BFS to Determine Component Infections (O(n^2) time, O(n) space)
Instead of Union-Find, traverse components directly using Depth-First Search or Breadth-First Search. Start from each unvisited node and perform a DFS/BFS to collect all nodes in that component. Track two values during traversal: the component size and how many nodes from initial appear in it. If exactly one infected node exists in the component, removing that node saves the entire component from infection. Maintain the best candidate by comparing saved component sizes and break ties using the smallest node index. This approach avoids the explicit disjoint set structure but still relies on the same core observation about connected components.
Recommended for interviews: The Union-Find approach is usually preferred because it cleanly models connected components and scales well for similar graph problems. Interviewers expect you to recognize that malware spreads across entire components. A DFS/BFS solution shows solid understanding of graph traversal, but Union-Find demonstrates stronger pattern recognition for component grouping problems.
One way to solve the problem is by using the Union-Find algorithm (also known as Disjoint Set Union or DSU) to identify connected components of the graph. Each component can either have one or more initially infected nodes. The objective is to remove a node such that the size of the initially infected nodes is minimized after malware spreads. This approach groups nodes together and calculates the effect of each removal by considering the infection spread of each distinct component.
The solution defines a Union-Find class with find and union methods to manage node groups efficiently. The minMalwareSpread method initiates a Union-Find instance, groups nodes, counts infections per component, sorts initial infections, and finds the best node to remove based on the unique infections that save the most nodes from being infected.
Time Complexity: O(n2) due to graph iteration, where n is the number of nodes. The union-find operations are nearly O(1) on average.
Space Complexity: O(n) for the union-find data structures.
This approach uses Depth-First Search (DFS) or Breadth-First Search (BFS) to analyze the graph, identify connected components, and determine component-wise infections. The solution calculates how many vertices are infected by each initial node within its component and selects a node for removal that would minimize the spread as much as possible.
This Python code uses BFS to find connected components and tags them. It processes components comparing infection counts and decides which node removal saves the most others from infection. Initial nodes are sorted for minimum index resolution on equal counts.
Python
C
JavaScript
Time Complexity: O(n2) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components.
According to the problem description, if there are several nodes in the same connected component initially, there can be three situations:
What we need to consider is to minimize the number of infected nodes left after removing a certain infected node.
For situation 1, there are no infected nodes, so we don't need to consider it; for situation 2, only one node is infected, so after removing this node, the other nodes in this connected component will not be infected; for situation 3, multiple nodes are infected, so after removing any infected node, the other nodes in this connected component will still be infected. Therefore, we only need to consider situation 2.
We use a union find set uf to maintain the connectivity of nodes, a variable ans to record the answer, and a variable mx to record the maximum number of infections that can be reduced currently. Initially, ans = n, mx = 0.
Then we traverse the array initial, use a hash table or an array of length n named cnt to count the number of infected nodes in each connected component.
Next, we traverse the array initial again. For each node x, we find the root node root of its connected component. If there is only one infected node in this connected component, i.e., cnt[root] = 1, we update the answer. The update condition is that the number of nodes sz in this connected component is greater than mx or sz equals mx and the value of x is less than ans.
Finally, if ans has not been updated, it means that there are multiple infected nodes in all connected components, so we return the minimum value in initial, otherwise, we return ans.
The time complexity is O(n^2 times \alpha(n)), and the space complexity is O(n). Where n is the number of nodes, and \alpha(n) is the inverse of the Ackermann function.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Union-Find to Segment Components | Time Complexity: O(n2) due to graph iteration, where n is the number of nodes. The union-find operations are nearly O(1) on average. |
| DFS/BFS to Determine Component Infections | Time Complexity: O(n2) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components. |
| Union Find | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find to Segment Components | O(n^2) | O(n) | Best general solution for adjacency matrix graphs and component grouping |
| DFS/BFS Component Traversal | O(n^2) | O(n) | Good when practicing graph traversal without extra data structures |
Minimize Malware Spread || Leetcode • Pepcoding • 9,392 views views
Watch 9 more video solutions →Practice Minimize Malware Spread with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor