Minimize Malware Spread — Hard Problem & Solution

Problem statement

A network of n machines is given as an n x n adjacency matrix graph, where graph[i][j] == 1 means machines i and j are directly connected (the matrix is symmetric and graph[i][i] == 1).

The machines listed in initial start out infected by malware. Whenever two directly connected machines include an infected one, the other becomes infected too; this continues until no more machines can be infected. Let M(initial) be the final number of infected machines.

You may remove exactly one machine from the initial list (it starts clean, but it can still be infected later through its connections). Return the machine whose removal minimises M(initial). If several machines tie, return the one with the smallest index.

Example 1

Input: graph = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]], initial = [3,0,2]
Output: 0
Explanation: Removing 0 saves the whole component {0, 1}; machines 2 and 3 would still infect each other.

Example 2

Input: graph = [[1,0,0],[0,1,1],[0,1,1]], initial = [2,0]
Output: 2
Explanation: Removing 2 saves two machines, removing 0 saves only one.

Example 3

Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [2,1]
Output: 1
Explanation: Either removal leaves everything infected; the smaller index wins.

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 - 1
• all the integers in initial are unique

How to solve Minimize Malware Spread

Infection saturates connected components. Cleaning one initial machine saves its component only when no other initial machine shares it, and then it saves the whole component.

Approach

1. Union every connected pair from the matrix and compute each component's size.
2. Count how many initial machines fall in each component.
3. For every initial machine, its saving is the component size if that component holds exactly one initial machine, else 0.
4. Return the machine with the largest saving, breaking ties by smallest index (this also covers the case where every saving is 0).

Why it works

The final infected set is the union of the components containing initial machines. Removing machine v changes that set only if v's component has no other initial machine, in which case exactly that component disappears from the union. So minimising M is maximising the saving, which these counts give directly.

Complexity

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

Pitfalls

• A removed machine is still in the network — if another initial machine shares its component, it gets reinfected and nothing is saved.
• When no removal saves anything, the answer is the smallest index in initial, which need not be its first element.
• Read connections from the matrix, not from initial alone.

Reference solution

Python

from typing import List

def minMalwareSpread(graph: List[List[int]], initial: List[int]) -> int:
    n = len(graph)
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for i in range(n):
        for j in range(i + 1, n):
            if graph[i][j] == 1:
                a, b = find(i), find(j)
                if a != b:
                    root[a] = b
    size = [0] * n
    for i in range(n):
        size[find(i)] += 1
    infected = [0] * n
    for v in initial:
        infected[find(v)] += 1
    best, best_save = -1, -1
    for v in sorted(initial):
        r = find(v)
        save = size[r] if infected[r] == 1 else 0
        if save > best_save:
            best, best_save = v, save
    return best

JavaScript

var minMalwareSpread = function(graph, initial) {
    var n = graph.length;
    var root = [], size = [], infected = [];
    for (var i = 0; i < n; i++) { root.push(i); size.push(0); infected.push(0); }
    var find = function(x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    for (var a = 0; a < n; a++) {
        for (var b = a + 1; b < n; b++) {
            if (graph[a][b] === 1) {
                var ra = find(a), rb = find(b);
                if (ra !== rb) root[ra] = rb;
            }
        }
    }
    for (var v = 0; v < n; v++) size[find(v)]++;
    for (var t = 0; t < initial.length; t++) infected[find(initial[t])]++;
    var best = -1, bestSave = -1;
    for (var s = 0; s < initial.length; s++) {
        var node = initial[s], r = find(node);
        var save = infected[r] === 1 ? size[r] : 0;
        if (save > bestSave || (save === bestSave && node < best)) { bestSave = save; best = node; }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard