Watch 10 video solutions for Minimize Malware Spread, a hard level problem involving Array, Hash Table, Depth-First Search. This walkthrough by Pepcoding has 9,392 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |