How hard is LeetCode 928. Minimize Malware Spread II?

LeetCode 928. Minimize Malware Spread II is rated Hard on LeetCode.

What is the time complexity of LeetCode 928. Minimize Malware Spread II?

The Python solution on this page runs in O(n^2 \times \alpha(n)).

What is the space complexity of LeetCode 928. Minimize Malware Spread II?

The Python solution on this page uses O(n^2) auxiliary space.

What topics does LeetCode 928. Minimize Malware Spread II cover?

LeetCode 928. Minimize Malware Spread II is tagged Depth-First Search, Breadth-First Search, Union Find, Graph, Array and Hash Table on LeetCode.

Minimize Malware Spread II — LeetCode 928 Python Solution

HardDepth-First SearchBreadth-First SearchUnion FindGraphArrayHash Table

Problem: #928
Pattern: Union-Find
Reading time: 9 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)
        s = set(initial)
        uf = UnionFind(n)
        for i in range(n):
            if i not in s:
                for j in range(i + 1, n):
                    graph[i][j] and j not in s and uf.union(i, j)

        g = defaultdict(set)
        cnt = Counter()
        for i in initial:
            for j in range(n):
                if j not in s and graph[i][j]:
                    g[i].add(uf.find(j))
            for root in g[i]:
                cnt[root] += 1

        ans, mx = 0, -1
        for i in initial:
            t = sum(uf.get_size(root) for root in g[i] if cnt[root] == 1)
            if t > mx or (t == mx and i < ans):
                ans, mx = i, t
        return ans

Complexity

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

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 928. Minimize Malware Spread II 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 928. Minimize Malware Spread II?: LeetCode 928. Minimize Malware Spread II is rated Hard on LeetCode.
What is the time complexity of LeetCode 928. Minimize Malware Spread II?: The Python solution on this page runs in O(n^2 \times \alpha(n)).
What is the space complexity of LeetCode 928. Minimize Malware Spread II?: The Python solution on this page uses O(n^2) auxiliary space.
What topics does LeetCode 928. Minimize Malware Spread II cover?: LeetCode 928. Minimize Malware Spread II is tagged Depth-First Search, Breadth-First Search, Union Find, Graph, Array and Hash Table on LeetCode.