How do you solve Minimize Malware Spread II on LeetCode?

Minimize Malware Spread II (LeetCode #928) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Understanding the spread of malware through connected components is crucial.

What is the brute force solution for Minimize Malware Spread II?

The brute force approach for Minimize Malware Spread II is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we will simulate the malware spread for each node in the initial list. By removing one node at a time, we can observe how many nodes remain infected after the spread, allowing us to determine the optimal node to remove. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Minimize Malware Spread II?

Clearly explain your thought process and approach before diving into coding. Consider edge cases, such as when all initial nodes are in the same component. Practice explaining your code and logic as you write to simulate interview conditions.

What are common mistakes when solving Minimize Malware Spread II?

Not considering the impact of each node's removal on the overall spread. Failing to account for the size of components when multiple nodes are infected.

#928

Minimize Malware Spread II

Hard

ArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryUnion-FindGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal approach utilizes a Union-Find data structure to efficiently group connected nodes. By tracking the size of each component, we can determine the impact of removing each initial node on the spread of malware without simulating the entire spread multiple times.

⚙️

Algorithm

3 steps

1Step 1: Use Union-Find to group connected nodes in the graph.
2Step 2: Count the size of each component that contains malware nodes.
3Step 3: For each initial node, calculate the total infected size if that node is removed, and track the minimum size and corresponding node.

solution.py49 lines

1class UnionFind:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.size = [1] * n
5
6    def find(self, x):
7        if self.parent[x] != x:
8            self.parent[x] = self.find(self.parent[x])
9        return self.parent[x]
10
11    def union(self, x, y):
12        rootX = self.find(x)
13        rootY = self.find(y)
14        if rootX != rootY:
15            if self.size[rootX] < self.size[rootY]:
16                rootX, rootY = rootY, rootX
17            self.parent[rootY] = rootX
18            self.size[rootX] += self.size[rootY]
19
20def minMalwareSpread(graph, initial):
21    n = len(graph)
22    uf = UnionFind(n)
23    for i in range(n):
24        for j in range(i + 1, n):
25            if graph[i][j] == 1:
26                uf.union(i, j)
27
28    component_size = defaultdict(int)
29    for node in range(n):
30        root = uf.find(node)
31        component_size[root] += 1
32
33    count = defaultdict(int)
34    for node in initial:
35        root = uf.find(node)
36        count[root] += 1
37
38    min_infected = float('inf')
39    best_node = -1
40    for node in initial:
41        root = uf.find(node)
42        if count[root] == 1:
43            infected_size = component_size[root]
44        else:
45            infected_size = 0
46        if infected_size < min_infected or (infected_size == min_infected and node < best_node):
47            min_infected = infected_size
48            best_node = node
49    return best_node

ℹ

Complexity note: The time complexity is O(n²) due to the nested loop for union operations in the Union-Find structure. The space complexity is O(n) because we maintain parent and size arrays for the Union-Find.

1Understanding the spread of malware through connected components is crucial.
2Using Union-Find can significantly optimize the process of grouping and counting nodes.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.