Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimize Malware Spread II solution and explanation

HardArrayBreadth-First SearchDepth-First SearchGraph8 min read46.2% acceptanceUpdated 9 Apr 2026
Asked atDropboxUber
Practise Minimize Malware Spread II
7:30
LeetCode 928. Minimize Malware Spread II Explanation and Solutionhappygirlzt · 7:30 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. LeetCode 928. Minimize Malware Spread II Explanation and Solutionhappygirlzt · 7:30 · 1K views
  2. Leetcode 928 Minimize Malware Spread II - Hard Coding Problem SolvedAlgorithmicIQ · 35:00 · 705 views
  3. 928. Minimize Malware Spread II (Leetcode Hard)Programming Live with Larry · 42:10 · 663 views
  4. 【每日一题】928. Minimize Malware Spread II, 10/08/2019Huifeng Guan · 38:33 · 515 views
  5. 928. Minimize Malware Spread II - Daily Leetcode (Day 4)yeetcode · 22:12 · 280 views
  6. Code Review: LeetCode 928: Minimize Malware Spread IIRoel Van de Paar · 2:55 · 26 views
  7. No Sound Leetcode 928: Minimize Malware Spread IIExtremeProgrammer · 3:36 · 18 views
  8. LeetCode 928 – Minimize Malware Spread IIujjwal painuly edit · 10:45 · 13 views
  9. LeetCode 928: Minimize Malware Spread IIAlitaCode · 32:14 · 4 views
  10. LeetCode Problem #928 Minimize Malware Spread II神戸万事屋 · 0:41

The problem

You are given a network of n nodes represented as an n x n adjacency matrix graph, where the ith node is directly connected to the jth 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.

Example 1:

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

Example 2:

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

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

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.

Approach overview

Problem Overview: You are given an undirected network represented by an adjacency matrix where some nodes are initially infected with malware. If two nodes are connected, infection spreads between them. You must remove exactly one initially infected node so the final number of infected nodes after the spread is minimized. If multiple choices give the same result, return the smallest index.

Approach 1: Brute Force Infection Simulation (O(k * n^2) time, O(n) space)

Try removing each node from the initial infected list one at a time. For every candidate removal, run a depth-first search or breadth-first search starting from the remaining infected nodes and simulate malware spread through the adjacency matrix. Count how many nodes end up infected. Track the removal that produces the smallest infected count. This approach directly models the spread but repeatedly traverses the graph, making it expensive when the number of infected nodes grows.

Approach 2: DFS Connected Components Analysis (O(n^2) time, O(n) space)

Instead of simulating spread repeatedly, analyze the structure of the graph. First identify connected components consisting only of clean nodes using DFS on the graph. For each component, track which infected nodes can reach it. If exactly one infected node connects to that component, removing that node prevents infection for the entire component. Sum the sizes of components uniquely controlled by each infected node and choose the node that saves the most vertices. This converts repeated spread simulation into a single component analysis pass.

Approach 3: Union-Find with Infected Tracking (O(n^2 * α(n)) time, O(n) space)

Use Union-Find to group all non-infected nodes into connected components. Iterate through the adjacency matrix and union clean nodes that share edges. Then examine edges between infected nodes and these clean components. For each component, count how many infected nodes can reach it. Components connected to exactly one infected node are "saved" if that infected node is removed. Accumulate the component sizes saved by each infected node and pick the best candidate. Union-Find keeps component size queries and merges efficient.

Recommended for interviews: The connected-component strategy (DFS or Union-Find) is the expected direction. Brute force simulation demonstrates understanding of the spread process, but interviewers typically look for the insight that only components uniquely infected by one node can be saved. Using DFS or Union-Find reduces repeated graph traversals and cleanly models the problem.

Approach 1: DFS Connected Components

In this approach, we utilize Depth-First Search (DFS) to determine connected components in the graph. We simulate the infection spread by considering how each initial node's removal would affect the overall spread of malware. The goal is to find the node whose removal results in the minimal spread of malware.

def minimizeMalwareSpread(graph, initial):
    n = len(graph)
    initial_set = set(initial)
    min_spread = float('inf')
    result = min(initial)
    
    def dfs(node):
        if visited[node]:
            return 0
        visited[node] = True
        count = 1
        for neighbor in range(n):
            if graph[node][neighbor] == 1 and neighbor not in initial_set:
                count += dfs(neighbor)
        return count
    
    for remove_node in initial:
        visited = [False] * n
        infected_count = 0

        for node in initial:
            if node != remove_node and not visited[node]:
                infected_count += dfs(node)

        if infected_count < min_spread or (infected_count == min_spread and remove_node < result):
            min_spread = infected_count
            result = remove_node

    return result
import java.util.*;

public class MinimizeMalwareSpread {
    public int minimizeMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        Set<Integer> initialSet = new HashSet<>();
        for (int node : initial) initialSet.add(node);

        boolean[] visited = new boolean[n];
        int minSpread = n, result = Arrays.stream(initial).min().orElse(-1);

        for (int removeNode : initial) {
            Arrays.fill(visited, false);
            int infectedCount = 0;

            for (int node : initial) {
                if (node != removeNode && !visited[node]) {
                    infectedCount += dfs(graph, node, visited, initialSet);
                }
            }

            if (infectedCount < minSpread || (infectedCount == minSpread && removeNode < result)) {
                minSpread = infectedCount;
                result = removeNode;
            }
        }
        return result;
    }

    private int dfs(int[][] graph, int node, boolean[] visited, Set<Integer> initialSet) {
        if (visited[node]) return 0;
        visited[node] = true;
        int count = 1;
        for (int neighbor = 0; neighbor < graph.length; neighbor++) {
            if (graph[node][neighbor] == 1 && !initialSet.contains(neighbor)) {
                count += dfs(graph, neighbor, visited, initialSet);
            }
        }
        return count;
    }
}
#include <vector>
#include <algorithm>

using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    for (int i = 0; i < graph.size(); i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

int minimizeMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
    int n = graph.size();
    int minMalwareSpread = n;
    int result = *min_element(initial.begin(), initial.end());
    
    for (int nodeToRemove : initial) {
        vector<bool> visited(n, false);
        int malwareCount = 0;

        for (int node : initial) {
            if (node != nodeToRemove && !visited[node]) {
                vector<bool> localVisited = visited;
                dfs(graph, localVisited, node);
                malwareCount += count(localVisited.begin(), localVisited.end(), true);
            }
        }

        if (malwareCount < minMalwareSpread || (malwareCount == minMalwareSpread && nodeToRemove < result)) {
            minMalwareSpread = malwareCount;
            result = nodeToRemove;
        }
    }

    return result;
}
function minimizeMalwareSpread(graph, initial) {
    const n = graph.length;
    let minSpread = Infinity, result = Math.min(...initial);

    function dfs(node, visited) {
        if (visited[node]) return 0;
        visited[node] = true;
        let count = 1;
        for (let neighbor = 0; neighbor < n; neighbor++) {
            if (graph[node][neighbor] === 1 && !visited[neighbor]) {
                count += dfs(neighbor, visited);
            }
        }
        return count;
    }

    for (let removeNode of initial) {
        const visited = Array(n).fill(false);
        let infectedCount = 0;

        for (let node of initial) {
            if (node !== removeNode && !visited[node]) {
                infectedCount += dfs(node, visited);
            }
        }

        if (infectedCount < minSpread || (infectedCount === minSpread && removeNode < result)) {
            minSpread = infectedCount;
            result = removeNode;
        }
    }

    return result;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void dfs(int** graph, int n, bool* visited, int current) {
    visited[current] = true;
    for (int i = 0; i < n; i++) {
        if (graph[current][i] == 1 && !visited[i]) {
            dfs(graph, n, visited, i);
        }
    }
}

int minimizeMalwareSpread(int** graph, int n, int* initial, int initialSize) {
    bool* visited = (bool*)calloc(n, sizeof(bool));
    int minMalwareSpread = n;
    int result = -1;
    
    for (int i = 0; i < initialSize; i++) {
        int removeNode = initial[i];
        int virusSpread = 0;
        for (int j = 0; j < n; j++) visited[j] = false;

        for (int j = 0; j < initialSize; j++) {
            if (i != j && !visited[initial[j]]) {
                dfs(graph, n, visited, initial[j]);
                for (int k = 0; k < n; k++) {
                    if (visited[k]) virusSpread++;
                }
            }
        }
        if (virusSpread < minMalwareSpread || (virusSpread == minMalwareSpread && removeNode < result)) {
            minMalwareSpread = virusSpread;
            result = removeNode;
        }
    }
    free(visited);
    return result;
}
using System;
using System.Collections.Generic;

public class Solution {
    public int MinimizeMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        Array.Sort(initial);
        int minSpread = int.MaxValue;
        int result = initial[0];

        foreach (var removeNode in initial) {
            bool[] visited = new bool[n];
            int infectedCount = 0;
            foreach (var node in initial) {
                if (node != removeNode && !visited[node]) {
                    infectedCount += DFS(graph, node, visited);
                }
            }

            if (infectedCount < minSpread || (infectedCount == minSpread && removeNode < result)) {
                minSpread = infectedCount;
                result = removeNode;
            }
        }
        return result;
    }

    private int DFS(int[][] graph, int node, bool[] visited) {
        if (visited[node]) return 0;
        visited[node] = true;
        int count = 1;
        for (int neighbor = 0; neighbor < graph.Length; neighbor++) {
            if (graph[node][neighbor] == 1 && !visited[neighbor]) {
                count += DFS(graph, neighbor, visited);
            }
        }
        return count;
    }
}

In the Python implementation, a DFS function recursively marks nodes as visited and counts them. The main function iterates over nodes in initial to simulate removing each node and computes the infection spread using DFS.

Complexity

Time Complexity: O(n^2 + k*n). Each initial node removal leads to DFS computation.
Space Complexity: O(n) for the visited nodes array.

Try this approach in the editor

Approach 2: Union-Find with Infected Tracking

In this approach, a Union-Find (or Disjoint Set Union) structure is used to maintain sets of nodes, helping to track connected components efficiently. We account for each component's size and how interconnected infected nodes influence the choice of node to remove.

def minimizeMalwareSpread(graph, initial):
    n = len(graph)
    initial.sort()
    parent = list(range(n))
    size = [1] * n
    infected_count = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            if size[rootX] > size[rootY]:
                parent[rootY] = rootX
            elif size[rootX] < size[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                size[rootX] += 1

    for i in range(n):
        for j in range(i + 1, n):
            if graph[i][j] == 1:
                union(i, j)

    for i in range(n):
        root = find(i)
        size[root] += 1

    for node in initial:
        root = find(node)
        infected_count[root] += 1

    result, max_saved = initial[0], 0
    for node in initial:
        root = find(node)
        if infected_count[root] == 1:
            if size[root] > max_saved:
                max_saved = size[root]
                result = node
            elif size[root] == max_saved and node < result:
                result = node

    return result
import java.util.*;

public class MinimizeMalwareSpread {
    public int minimizeMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] parent = new int[n], size = new int[n], rank = new int[n];
        Arrays.setAll(parent, i -> i);
        Arrays.fill(size, 1);
        int[] infectedCount = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    union(parent, rank, i, j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            int root = find(parent, i);
            size[root]++;
        }

        for (int node : initial) {
            int root = find(parent, node);
            infectedCount[root]++;
        }

        Arrays.sort(initial);
        int result = initial[0], maxSaved = 0;

        for (int node : initial) {
            int root = find(parent, node);
            if (infectedCount[root] == 1) {
                if (size[root] > maxSaved) {
                    maxSaved = size[root];
                    result = node;
                } else if (size[root] == maxSaved && node < result) {
                    result = node;
                }
            }
        }

        return result;
    }

    private int find(int[] parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }

    private void union(int[] parent, int[] rank, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int find(vector<int>& parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }

    void unionNodes(vector<int>& parent, vector<int>& rank, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    int minimizeMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<int> parent(n);
        vector<int> rank(n, 0), size(n, 1), infectedCount(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    unionNodes(parent, rank, i, j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            int root = find(parent, i);
            size[root]++;
        }

        for (int node : initial) {
            int root = find(parent, node);
            infectedCount[root]++;
        }

        sort(initial.begin(), initial.end());
        int result = initial[0], maxSaved = 0;

        for (int node : initial) {
            int root = find(parent, node);
            if (infectedCount[root] == 1) {
                if (size[root] > maxSaved) {
                    maxSaved = size[root];
                    result = node;
                } else if (size[root] == maxSaved && node < result) {
                    result = node;
                }
            }
        }

        return result;
    }
};
function minimizeMalwareSpread(graph, initial) {
    const n = graph.length;
    const parent = Array.from({ length: n }, (_, i) => i);
    const size = new Array(n).fill(1);
    const infectedCount = new Array(n).fill(0);
    initial.sort((a, b) => a - b);

    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            parent[rootY] = rootX;
        }
    }

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (graph[i][j] === 1) {
                union(i, j);
            }
        }
    }

    for (let i = 0; i < n; i++) {
        const root = find(i);
        size[root]++;
    }

    for (let node of initial) {
        const root = find(node);
        infectedCount[root]++;
    }

    let result = initial[0], maxSaved = 0;
    for (let node of initial) {
        const root = find(node);
        if (infectedCount[root] === 1) {
            if (size[root] > maxSaved) {
                maxSaved = size[root];
                result = node;
            } else if (size[root] === maxSaved && node < result) {
                result = node;
            }
        }
    }

    return result;
}
#include <stdio.h>
#include <stdlib.h>

int find(int* parent, int i) {
    if (parent[i] != i) {
        parent[i] = find(parent, parent[i]);
    }
    return parent[i];
}

void unionNodes(int* parent, int* rank, int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

int minimizeMalwareSpread(int** graph, int n, int* initial, int initialSize) {
    int* parent = (int*)malloc(n * sizeof(int));
    int* rank = (int*)calloc(n, sizeof(int));
    int* size = (int*)calloc(n, sizeof(int));
    int* infectedCount = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j]) {
                unionNodes(parent, rank, i, j);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        int root = find(parent, i);
        size[root]++;
    }

    for (int i = 0; i < initialSize; i++) {
        int root = find(parent, initial[i]);
        infectedCount[root]++;
    }

    int result = n, maxSaved = 0;
    for (int i = 0; i < initialSize; i++) {
        int node = initial[i];
        int root = find(parent, node);
        if (infectedCount[root] == 1) {
            if (size[root] > maxSaved) {
                maxSaved = size[root];
                result = node;
            } else if (size[root] == maxSaved && node < result) {
                result = node;
            }
        }
    }
    free(parent);
    free(rank);
    free(size);
    free(infectedCount);
    return result;
}
using System;
using System.Linq;

public class Solution {
    public int MinimizeMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        var parent = Enumerable.Range(0, n).ToArray();
        var size = new int[n];
        var infectedCount = new int[n];

        Array.Sort(initial);

        int Find(int i) {
            if (parent[i] != i) {
                parent[i] = Find(parent[i]);
            }
            return parent[i];
        }

        void Union(int x, int y) {
            int rootX = Find(x);
            int rootY = Find(y);
            if (rootX != rootY) {
                if (size[rootX] > size[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootX] = rootY;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    Union(i, j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            int root = Find(i);
            size[root]++;
        }

        foreach (var node in initial) {
            int root = Find(node);
            infectedCount[root]++;
        }

        int result = initial[0], maxSaved = 0;

        foreach (var node in initial) {
            int root = Find(node);
            if (infectedCount[root] == 1) {
                if (size[root] > maxSaved) {
                    maxSaved = size[root];
                    result = node;
                } else if (size[root] == maxSaved && node < result) {
                    result = node;
                }
            }
        }

        return result;
    }
}

In this Python solution, Union-Find assists in clustering nodes into connected groups. We determine which component maximally benefits from the removal of an infected node, selecting the optimal candidate for removal.

Complexity

Time Complexity: O(n^2) for component connections and unions.
Space Complexity: O(n) due to array storage for parent, size, and infection counts.

Try this approach in the editor

Approach 3: Union-Find

We can use the union-find data structure to merge all nodes that are not in initial and satisfy graph[i][j] = 1.

Next, we create a hash table g, where g[i] represents the root node of the connected component that is connected to node i. We also need a counter cnt to count how many initial nodes each root node is infected by.

For each initially infected node i, we traverse all nodes j connected to node i. If node j is not in initial, we add the root node of node j to the set g[i]. At the same time, we count how many initial nodes each root node is infected by and save the result in the counter cnt.

Then, we use a variable ans to record the answer, and mx to record the maximum number of infected nodes that can be reduced. Initially, ans = 0, mx = -1.

We traverse all initially infected nodes. For each node i, we traverse all root nodes in g[i]. If a root node is only infected by one initial node, we add the size of the connected component where the root node is located to t. If t > mx or t = mx and i < ans, we update ans = i, mx = t.

Finally, we return ans.

The time complexity is O(n^2 times \alpha(n)), and the space complexity is O(n^2). Where n is the number of nodes, and \alpha(n) is the inverse Ackermann function.

class UnionFind {
    p: number[];
    size: number[];
    constructor(n: number) {
        this.p = Array(n)
            .fill(0)
            .map((_, i) => i);
        this.size = Array(n).fill(1);
    }

    find(x: number): number {
        if (this.p[x] !== x) {
            this.p[x] = this.find(this.p[x]);
        }
        return this.p[x];
    }

    union(a: number, b: number): boolean {
        const [pa, pb] = [this.find(a), this.find(b)];
        if (pa === pb) {
            return false;
        }
        if (this.size[pa] > this.size[pb]) {
            this.p[pb] = pa;
            this.size[pa] += this.size[pb];
        } else {
            this.p[pa] = pb;
            this.size[pb] += this.size[pa];
        }
        return true;
    }

    getSize(root: number): number {
        return this.size[root];
    }
}

function minMalwareSpread(graph: number[][], initial: number[]): number {
    const n = graph.length;
    const s = new Set(initial);
    const uf = new UnionFind(n);
    for (let i = 0; i < n; ++i) {
        if (!s.has(i)) {
            for (let j = i + 1; j < n; ++j) {
                if (graph[i][j] && !s.has(j)) {
                    uf.union(i, j);
                }
            }
        }
    }
    const g: Set<number>[] = Array.from({ length: n }, () => new Set());
    const cnt: number[] = Array(n).fill(0);
    for (const i of initial) {
        for (let j = 0; j < n; ++j) {
            if (graph[i][j] && !s.has(j)) {
                g[i].add(uf.find(j));
            }
        }
        for (const root of g[i]) {
            ++cnt[root];
        }
    }
    let ans = 0;
    let mx = -1;
    for (const i of initial) {
        let t = 0;
        for (const root of g[i]) {
            if (cnt[root] === 1) {
                t += uf.getSize(root);
            }
        }
        if (t > mx || (t === mx && i < ans)) {
            [ans, mx] = [i, t];
        }
    }
    return ans;
}
type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func (uf *unionFind) getSize(root int) int {
	return uf.size[root]
}

func minMalwareSpread(graph [][]int, initial []int) int {
	n := len(graph)
	s := make([]bool, n)
	for _, i := range initial {
		s[i] = true
	}
	uf := newUnionFind(n)
	for i := range graph {
		if !s[i] {
			for j := i + 1; j < n; j++ {
				if graph[i][j] == 1 && !s[j] {
					uf.union(i, j)
				}
			}
		}
	}
	g := make([]map[int]bool, n)
	for _, i := range initial {
		g[i] = map[int]bool{}
	}
	cnt := make([]int, n)
	for _, i := range initial {
		for j := 0; j < n; j++ {
			if !s[j] && graph[i][j] == 1 {
				g[i][uf.find(j)] = true
			}
		}
		for root := range g[i] {
			cnt[root]++
		}
	}
	ans, mx := 0, -1
	for _, i := range initial {
		t := 0
		for root := range g[i] {
			if cnt[root] == 1 {
				t += uf.getSize(root)
			}
		}
		if t > mx || t == mx && i < ans {
			ans, mx = i, t
		}
	}
	return ans
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
DFS Connected Components

Time Complexity: O(n^2 + k*n). Each initial node removal leads to DFS computation.
Space Complexity: O(n) for the visited nodes array.

Union-Find with Infected Tracking

Time Complexity: O(n^2) for component connections and unions.
Space Complexity: O(n) due to array storage for parent, size, and infection counts.

Union-Find–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force Infection SimulationO(k * n^2)O(n)Good for understanding malware spread mechanics or small graphs
DFS Connected ComponentsO(n^2)O(n)Preferred when using graph traversal to analyze clean components
Union-Find with Infected TrackingO(n^2 α(n))O(n)Best when managing connected components efficiently with repeated merges

Frequently asked questions

Is Minimize Malware Spread II easy or hard?

Minimize Malware Spread II is classified as Hard on LeetCode. The challenge is recognizing that brute-force infection simulation is inefficient and that analyzing connected components of clean nodes reveals which infected node removal minimizes total spread.

How to solve Minimize Malware Spread II in O(n^2)?

First isolate connected components of non-infected nodes using DFS or Union-Find. For each component, count how many infected nodes have edges to it. If exactly one infected node reaches that component, removing that node prevents infection of the entire component. Choose the infected node that uniquely infects the largest number of nodes.

What is the best approach for Minimize Malware Spread II?

Connected component analysis using DFS or Union-Find is the most effective approach. Group clean nodes into components and track which infected nodes can reach each component. If a component is connected to exactly one infected node, removing that node prevents the entire component from getting infected. This reduces repeated spread simulations and runs in about O(n^2) time.

Is Minimize Malware Spread II asked at Google/Amazon/Meta?

Graph infection and component analysis problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving Union-Find, BFS, or DFS over adjacency matrices are common in system modeling and graph reasoning questions.

What data structure is used in Minimize Malware Spread II?

The problem relies on graph data structures represented by an adjacency matrix. Typical solutions use depth-first search (DFS), breadth-first search (BFS), or the Union-Find (Disjoint Set Union) structure to track connected components and infection reachability.

What is the time complexity of Minimize Malware Spread II?

The optimal solutions run in O(n^2) time because the graph is represented as an n x n adjacency matrix. DFS-based component analysis scans the matrix once, while Union-Find performs near-constant merges with α(n) overhead. Space complexity is O(n) for component tracking and bookkeeping.

Minimize Malware Spread II Python or Java solution approach?

Python and Java implementations usually build connected components using DFS or Union-Find. After grouping clean nodes, maintain counts of infected neighbors for each component and compute how many nodes each infected vertex uniquely infects. The node saving the most vertices is returned.

Comments

Now write it yourselfClose this page and solve Minimize Malware Spread II in the editor, without looking.
Practise Minimize Malware Spread II