HardNo. 0924
Minimize Malware Spread — LeetCode 924 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph, Array, Hash Table
- Reading time
- 8 min
- Source
- leetcode.com
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.
Example
- Input
- graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
- Output
- 0
Python solution
class UnionFind:
__slots__ = "p", "size"
def __init__(self, n: int):
self.p = list(range(n))
self.size = [1] * n
def find(self, x: int) -> int:
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a: int, b: int) -> bool:
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
def get_size(self, root: int) -> int:
return self.size[root]
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
graph[i][j] and uf.union(i, j)
cnt = Counter(uf.find(x) for x in initial)
ans, mx = n, 0
for x in initial:
root = uf.find(x)
if cnt[root] > 1:
continue
sz = uf.get_size(root)
if sz > mx or (sz == mx and x < ans):
ans = x
mx = sz
return min(initial) if ans == n else ansComplexity
- Time
- O(n2 × α(n))
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 924. Minimize Malware Spread is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0928 | Minimize Malware Spread II | Hard |
| 2368 | Reachable Nodes With Restrictions | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0959 | Regions Cut By Slashes | Medium |
| 1202 | Smallest String With Swaps | Medium |
Frequently asked questions
- How hard is LeetCode 924. Minimize Malware Spread?
LeetCode 924. Minimize Malware Spread is rated Hard on LeetCode.
- What is the time complexity of LeetCode 924. Minimize Malware Spread?
The Python solution on this page runs in O(n2 × α(n)).
- What is the space complexity of LeetCode 924. Minimize Malware Spread?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 924. Minimize Malware Spread cover?
LeetCode 924. Minimize Malware Spread is tagged Depth-First Search, Breadth-First Search, Union Find, Graph, Array and Hash Table on LeetCode.