Course4all

Minimize Malware Spread

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

Minimize Malware Spread

In a network of nn nodes, some nodes are initially infected with malware. Malware spreads through connected components. You can remove exactly one node from the initial list to minimize total infected nodes. If multiple nodes lead to the same result, return the node with the smallest index.

Optimization Strategy

Only removing an infected node in a component with exactly one initially infected node will actually reduce the total infection (by the size of that component).
Hard

Examples

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

Level II: DFS (Component Analysis)

Intuition

Use DFS to find all connected components in the graph. For each component, count how many nodes in initial are part of it. If only one node is infected, removing it saves all nodes in that component. Track the best node to remove.
⏱ O(N^2).💾 O(N).
java
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length; int[] comp = new int[n]; Arrays.fill(comp, -1); int ids = 0;
        for(int i=0; i<n; i++) if(comp[i]==-1) dfs(graph, i, comp, ids++);
        int[] sz = new int[ids], mal = new int[ids];
        for(int i=0; i<n; i++) sz[comp[i]]++;
        for(int i : initial) mal[comp[i]]++;
        Arrays.sort(initial); int res = initial[0], maxS = -1;
        for(int i : initial) {
            if(mal[comp[i]]==1 && sz[comp[i]] > maxS) { maxS = sz[comp[i]]; res = i; }
        }
        return res;
    }
    void dfs(int[][] g, int u, int[] comp, int id) {
        comp[u] = id; for(int v=0; v<g.length; v++) if(g[u][v]==1 && comp[v]==-1) dfs(g, v, comp, id);
    }
}
Approach 2

Level III: Union-Find (Component Size Analysis)

Intuition

Build components using Union-Find and record the size of each. For each component, count how many nodes from initial are in it. If a component has exactly one initial node, moving that node saves size nodes. Pick the one that saves the most.
⏱ O(N^2) to build graph components.💾 O(N).
java
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] p = new int[n]; for(int i=0; i<n; i++) p[i]=i;
        int[] sz = new int[n]; Arrays.fill(sz, 1);
        for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(graph[i][j]==1) union(p, sz, i, j);
        int[] count = new int[n];
        for(int i : initial) count[find(p, i)]++;
        Arrays.sort(initial);
        int res = initial[0], maxSave = -1;
        for(int i : initial) {
            int root = find(p, i);
            if(count[root] == 1) {
                if(sz[root] > maxSave) { maxSave = sz[root]; res = i; }
            }
        }
        return res;
    }
    int find(int[] p, int i) { return p[i]==i ? i : (p[i]=find(p, p[i])); }
    void union(int[] p, int[] sz, int i, int j) {
        int r1=find(p,i), r2=find(p,j);
        if(r1 != r2) { p[r1]=r2; sz[r2]+=sz[r1]; }
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionRegions Cut By Slashes
Next Question →Making a Large Island