How do you solve Minimize Malware Spread on LeetCode?

Minimize Malware Spread (LeetCode #924) 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 connected components is crucial for solving graph-related problems.

What is the brute force solution for Minimize Malware Spread?

The brute force approach for Minimize Malware Spread is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves simulating the removal of each infected node one by one and calculating the total number of nodes infected after the spread. This is straightforward but inefficient as it checks every possibility. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Minimize Malware Spread?

Always clarify the problem statement and constraints before diving into coding. Discuss your thought process and approach with the interviewer to demonstrate your understanding. Practice implementing Union-Find and other graph algorithms, as they are commonly used in interview questions.

What are common mistakes when solving Minimize Malware Spread?

Not properly handling the case where multiple nodes can lead to the same minimum infection count. Failing to account for the fact that a node can still be infected after removal if it connects to other infected nodes.

#924

Minimize Malware Spread

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 solution uses a Union-Find (Disjoint Set Union) to efficiently group connected components and track the spread of malware. This allows us to determine the impact of removing each infected node without redundant calculations.

⚙️

Algorithm

4 steps

1Step 1: Use Union-Find to group nodes into connected components based on the graph.
2Step 2: Count the number of initially infected nodes in each component.
3Step 3: For each infected node, calculate the total number of infected nodes if that node is removed.
4Step 4: Track the minimum number of infected nodes and the corresponding node index.

solution.py51 lines

1class UnionFind:
2    def __init__(self, size):
3        self.parent = list(range(size))
4        self.rank = [1] * size
5
6    def find(self, u):
7        if self.parent[u] != u:
8            self.parent[u] = self.find(self.parent[u])
9        return self.parent[u]
10
11    def union(self, u, v):
12        rootU = self.find(u)
13        rootV = self.find(v)
14        if rootU != rootV:
15            if self.rank[rootU] > self.rank[rootV]:
16                self.parent[rootV] = rootU
17            elif self.rank[rootU] < self.rank[rootV]:
18                self.parent[rootU] = rootV
19            else:
20                self.parent[rootV] = rootU
21                self.rank[rootU] += 1
22
23def minMalwareSpread(graph, initial):
24    n = len(graph)
25    uf = UnionFind(n)
26    for i in range(n):
27        for j in range(i + 1, n):
28            if graph[i][j] == 1:
29                uf.union(i, j)
30
31    component_count = defaultdict(int)
32    infected_count = defaultdict(int)
33    for node in initial:
34        root = uf.find(node)
35        infected_count[root] += 1
36
37    for node in range(n):
38        root = uf.find(node)
39        component_count[root] += 1
40
41    min_infected = float('inf')
42    result_node = -1
43    for node in initial:
44        root = uf.find(node)
45        if infected_count[root] == 1:
46            if min_infected > component_count[root]:
47                min_infected = component_count[root]
48                result_node = node
49            elif min_infected == component_count[root]:
50                result_node = min(result_node, node)
51    return result_node

ℹ

Complexity note: The time complexity is O(n²) due to the nested loops for union operations, while the space complexity is O(n) for storing parent and rank arrays in the Union-Find structure.

1Understanding connected components is crucial for solving graph-related problems.
2Using Union-Find can significantly optimize the process of grouping nodes and tracking their connections.

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