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(n^2 \times \alpha(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.

Minimize Malware Spread — LeetCode 924 Python Solution

HardDepth-First SearchBreadth-First SearchUnion FindGraphArrayHash Table

Problem: #924
Pattern: Union-Find
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

Python

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 ans

Complexity

Measure	Complexity
Time	O(n^2 \times \alpha(n))
Space	O(n) auxiliary

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.

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(n^2 \times \alpha(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.