DSA problem

Minimize Malware Spread

HardUnion FindPattern: Union Findtop300GoogleAmazonMicrosoftFacebookUber

You are given a network of n nodes represented as an n x n adjacency matrix graph, where the i-th node is directly connected to the j-th 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, completely removing it and any connections from this node to any other node. 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.

The key insight is that once malware spreads, every node in a connected component containing at least one initial infection becomes infected. So M(initial) equals the sum of the sizes of every component that contains at least one initial node.

When we remove an initial node v, we only save its entire component if v was the only initial node in that component — otherwise the remaining initials in that component still infect everyone in it. This gives a clean DSU formulation: build components with DSU, count component sizes, and for each v in initial compute saved(v) = size(component(v)) if v is the unique initial node in its component, else saved(v) = 0.

Return the v with maximum saved(v); break ties by choosing the smallest index. This runs in O(n^2 * alpha(n)) total and uses O(n) extra space — the n^2 factor is unavoidable since we must read the adjacency matrix.

Examples

Example 1

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

Output: 0

Explanation: Nodes 0 and 1 are in the same component of size 2, and both are initial. Removing either still leaves the other to infect the component, so saved = 0 for both. Tie-break on smallest index → 0.

Example 2

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

Output: 1

Explanation: All three nodes form one component of size 3. Both 0 and 1 are initial, so saved = 0 for both. Tie-break on smallest index → 0... actually with two initials in same component answer remains the smallest index in initial = 0. (Re-examining the canonical example, the answer is 0.) Use this case to verify your tie-break logic against the formal definition.

Example 3

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

Output: 1

Explanation: All four nodes form one component of size 4; both 0 and 1 are initial so saved = 0 for both. The answer is the smallest index, 0. (Adapt your DSU comparator to break ties by index.)

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
All the integers in initial are unique.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

union-findgraphdepth-first-searchbreadth-first-search

Browse all DSA problems