Minimize Malware Spread

HardUnion-Find · Connected Components🧩 Union-Find LeetCode #924 ↗Updated Oct 30, 2026

Problem

A network of n machines is given as a symmetric adjacency matrix graph (graph[i][j] == 1 means a direct link). The machines in initial are infected, and malware spreads along links until nothing new can be reached. You may remove exactly one machine from initial (it stays in the network and can still be reinfected). Return the machine whose removal leaves the fewest infected machines; break ties by the smallest index.

Inputgraph = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]], initial = [2,0]Output0

Inputgraph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,2]Output0

Inputgraph = [[1,0,0],[0,1,1],[0,1,1]], initial = [2,0]Output2

2 ≤ n ≤ 300 · graph[i][i] = 1, graph symmetric · 1 ≤ initial.length ≤ n · initial values distinct

Try it yourself

Java

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Malware fills whole connected components. Removing a node only helps if it is the only initially infected node in its component — then the entire component is saved. So pick the uniquely-infected component with the largest size.

PatternUnion-Find

Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.

Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).

Open the Union-Find guide →

Approaches

Brute ForceSimulate Every Removal

Time O(k·n²)Space O(n)

For each candidate in initial (in ascending order), run a multi-source BFS from the other infected machines on the matrix and count how many end up infected. Keep the candidate with the smallest count; scanning in ascending order with a strict < settles ties. k = |initial|.

Java

public int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    int[] candidates = initial.clone();
    Arrays.sort(candidates);
    int best = candidates[0], bestCount = Integer.MAX_VALUE;
    for (int removed : candidates) {
        boolean[] infected = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        for (int s : initial) {
            if (s != removed) {
                infected[s] = true;
                queue.add(s);
            }
        }
        int count = queue.size();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v = 0; v < n; v++) {
                if (graph[u][v] == 1 && !infected[v]) {
                    infected[v] = true;
                    count++;
                    queue.add(v);
                }
            }
        }
        if (count < bestCount) {
            bestCount = count;
            best = removed;
        }
    }
    return best;
}

Faithful to the statement, but up to n BFS runs of O(n²) each.

OptimalUnion-Find Component Sizes

Time O(n²·α(n))Space O(n)

Union every linked pair to get components and their sizes, then count how many initial machines fall in each component. Among initial machines whose component contains exactly one infected machine, the best removal saves the largest component (smallest index on ties). If none is unique, nothing can be saved, so return the smallest index in initial.

Java

public int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    int[] parent = new int[n];
    int[] size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j] == 1) union(parent, size, i, j);
        }
    }
    int[] infectedIn = new int[n]; // infected count per component root
    for (int s : initial) infectedIn[find(parent, s)]++;
    int best = -1, bestSaved = -1, smallest = Integer.MAX_VALUE;
    for (int s : initial) {
        smallest = Math.min(smallest, s);
        int root = find(parent, s);
        if (infectedIn[root] != 1) continue; // removing s saves nobody
        int saved = size[root];
        if (saved > bestSaved || (saved == bestSaved && s < best)) {
            bestSaved = saved;
            best = s;
        }
    }
    return best == -1 ? smallest : best;
}

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

private void union(int[] parent, int[] size, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return;
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    size[ra] += size[rb];
}

One pass over the matrix — reading the input already costs O(n²).

Pro tip

A DFS that labels components works equally well here; union-find just makes the component size available as a by-product of the unions.

At a glance

Level	Approach	Time	Space
Brute Force	Simulate Every Removal	`O(k·n²)`	`O(n)`
Optimal	Union-Find Component Sizes	`O(n²·α(n))`	`O(n)`

Common pitfalls

Picking the largest component even when it holds 2+ infected nodes — removal saves nothing there.
Forgetting the fallback: if no component is uniquely infected, return min(initial).
Assuming initial is sorted — tie-breaks must use the actual smallest index.

Interview tips

Explain the observation first: infection is “all or nothing” per component.
Walk through the tie-break and fallback cases explicitly; they are where bugs hide.
Mention the harder variant (LC 928) where the removed node is deleted from the graph.

Pattern

Union-Find with component sizes → questions whose effect spreads across an entire connected component.

My notes saved in this browser