Minimize Malware Spread
Last Updated: March 28, 2026
Understanding the Problem
The problem boils down to: given an undirected graph and a set of initially infected nodes, figure out which single node's removal from the initial set would leave the fewest total infected nodes after the malware finishes spreading.
The critical insight is that malware spreads across entire connected components. If a connected component contains at least one initially infected node, every node in that component will eventually be infected. So the question becomes: which initially infected node, when removed, would "save" the most nodes from infection?
Here's where it gets interesting. Removing an initially infected node only saves its component if that node is the sole initially infected node in that component. If a component has two or more nodes from initial, removing just one of them won't help because the other one will still infect the entire component. So the best candidate for removal is the node that's the only initially infected node in its component, and whose component is the largest.
Key Constraints:
2 <= n <= 300→ With n up to 300, the adjacency matrix has at most 90,000 entries. O(n^2) is perfectly fine, and even O(n^3) would be under 27 million operations.graph[i][j] == graph[j][i]→ Undirected graph. We can use Union Find without worrying about edge direction.1 <= initial.length <= n→ The initial set can be as large as the entire graph. Edge case: every node might be initially infected.
Approach 1: Brute Force (Simulate Each Removal)
Intuition
The most direct approach: try removing each node from initial one at a time, simulate the malware spread using BFS, and count how many nodes end up infected. Pick the removal that yields the fewest infections.
For each candidate node to remove, we create a modified initial set (excluding that node), then run BFS from every remaining initially infected node to find all reachable nodes. The total number of reachable nodes is the infection count for that removal.
Algorithm
- Sort the
initialarray (so we naturally handle tie-breaking by smallest index). - For each node
removeNodeininitial:
a. Create a set of remaining infected nodes = initial minus removeNode.
b. Run BFS from all remaining infected nodes to count total infected nodes.
- Return the
removeNodethat resulted in the smallest infection count.
Example Walkthrough
Code
- Time Complexity: O(k * n^2). For each of the k nodes in initial, we run a BFS that visits up to n nodes, checking all n neighbors for each. Since k can be up to n, worst case is O(n^3).
- Space Complexity: O(n). The infected array and BFS queue use O(n) space.
We're running a full BFS for every node in initial, but the component structure doesn't change between removals. What if we computed the connected components just once?
Approach 2: Connected Components (DFS)
Intuition
Here's the key observation that makes this problem elegant: malware spreads across entire connected components. If any node in a component is initially infected, all nodes in that component become infected. So we only need to think at the component level.
The question becomes: for each connected component, how many nodes from initial does it contain?
- If a component contains zero nodes from
initial, it stays clean regardless of what we remove. - If a component contains exactly one node from
initial, removing that node saves the entire component from infection. - If a component contains two or more nodes from
initial, removing any one of them doesn't help because the others will still infect the whole component.
So the optimal node to remove is the one that's the sole infected node in the largest component. If no node is uniquely responsible for infecting its component, every removal saves zero nodes, and we return the smallest index in initial.
The insight is that malware spreads through connected components completely. Once any node in a component is infected, all nodes are infected. So the only way removing a node from initial can save nodes is if that node was the sole reason its component was infected in the first place.
If a component has two infected nodes and you remove one, the other still infects the whole component. You saved nothing. But if a component has exactly one infected node, removing it means no node in that component starts with malware, and the component stays clean.
Algorithm
- Find all connected components using DFS. Assign each node a component ID and compute each component's size.
- For each component, count how many nodes from
initialbelong to it. - For each node in
initial: if it's the only initially infected node in its component, its "savings" equals the component size. - Return the node with the highest savings. Break ties by returning the smallest index.
Example Walkthrough
Code
- Time Complexity: O(n^2). Finding connected components with DFS takes O(n^2) since we examine every edge in the adjacency matrix. The subsequent counting and comparison steps are O(n) or O(k).
- Space Complexity: O(n). We store component IDs, sizes, and initial counts, each requiring O(n) space.
The DFS approach works well but requires explicit stack management. Union Find can build the same component structure more elegantly.
Approach 3: Union Find (Optimal)
Intuition
Union Find is a natural fit for connected component problems. Instead of running DFS to discover components, we can scan the adjacency matrix and union nodes that are connected. After processing all edges, nodes in the same component share the same root. We can then query component sizes and count initial nodes per component in a single pass.
The logic is identical to Approach 2: find a node in initial that's the sole infected node in its component, and pick the one in the largest component. Union Find just gives us a more elegant way to find and track components.
Algorithm
- Initialize a Union Find structure with n nodes.
- Scan the adjacency matrix. For each edge
graph[i][j] == 1wherei < j, union nodesiandj. - After all unions, for each node in
initial, find its root (component representative). - Count how many nodes from
initialshare each root. Also track each component's total size. - Iterate through
initial(sorted). For each node whose component has exactly 1 initial node, its savings equals the component size. - Return the node with the highest savings, breaking ties by smallest index.
Example Walkthrough
Code
- Time Complexity: O(n^2 * alpha(n)). Scanning the adjacency matrix takes O(n^2). Each union/find operation costs O(alpha(n)) amortized, which is effectively constant. Total is essentially O(n^2).
- Space Complexity: O(n). The parent and rank arrays each use O(n) space. Component size and initial count arrays also use O(n).