#928

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimize Malware Spread II

Minimize Malware Spread II asks to minimize the spread of malware in a network of nodes by removing one infected node.

array hash table depth first search breadth first search union find

Problem Statement

In this problem, you are given a network represented as an adjacency matrix graph of size n x n. Each node in the graph can be connected to other nodes, and some nodes are initially infected by malware. When a node is infected, it spreads malware to any directly connected node. Your goal is to minimize the spread of malware by removing exactly one node from the initially infected set.

After removing one infected node, the spread of malware continues. You need to find which node, when removed, results in the minimum number of infected nodes. If multiple nodes lead to the same result, return the node with the smallest index. The task involves simulating the malware spread to find the optimal node for removal.

Examples

Example 1

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]

Output: 0

Example details omitted.

Example 2

Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]

Output: 1

Example details omitted.

Example 3

Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]

Output: 1

Example details omitted.

Constraints

n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] is 0 or 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length < n
0 <= initial[i] <= n - 1
All the integers in initial are unique.

Solution Approach

Graph Traversal and Simulation

Use DFS or BFS to simulate the spread of malware from the initially infected nodes. By traversing the graph, mark all the nodes infected by malware. Then, for each infected node, temporarily remove it from the initial set and simulate the spread again, calculating the number of infected nodes after removal.

Node Impact Assessment

For each infected node, assess how its removal impacts the number of newly infected nodes by considering the connections between nodes. Use hash lookups to track the infection status and calculate how the network's connectivity changes after removing an infected node.

Choose the Optimal Node

After evaluating the impact of each infected node's removal, choose the node that minimizes the total number of infected nodes. In case of a tie, return the node with the smallest index, ensuring that the solution is both optimal and efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of nodes (n) and the number of connections. The approach involves simulating the spread of malware multiple times, leading to a time complexity of O(n^2) for graph traversal. The space complexity is also O(n^2) due to the storage of the adjacency matrix and infection states.

What Interviewers Usually Probe

The candidate demonstrates knowledge of graph traversal algorithms like DFS and BFS.
The candidate can efficiently evaluate the impact of node removal in a graph with multiple infected nodes.
The candidate correctly optimizes for the minimum number of infections after node removal.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the spread of malware from all initially infected nodes and only considering the first infected node.
Overlooking edge cases where removing a node does not reduce the number of infections.
Not properly simulating the infection spread after node removal, leading to incorrect calculations of the final result.

Follow-up variants

Consider variations where the number of initially infected nodes can vary or where different network topologies are used.
Extend the problem to handle multiple malware types or sources of infection.
Alter the problem to allow multiple nodes to be removed and find the combination that minimizes malware spread.

FAQ

How do I minimize malware spread in a network of nodes?

To minimize malware spread, you must determine which infected node to remove. Use graph traversal techniques like DFS or BFS to simulate the spread and assess the impact of removing each infected node.

What graph traversal techniques can I use for this problem?

You can use DFS (Depth-First Search) or BFS (Breadth-First Search) to traverse the graph and simulate the spread of malware, ensuring that all connections are considered when assessing node removal.

What should I do if multiple nodes result in the same infection count?

If multiple nodes lead to the same reduction in infection count, return the node with the smallest index to ensure an optimal solution.

How does removing a node affect the malware spread?

Removing a node reduces the number of nodes it can spread malware to, potentially halting the infection from reaching connected nodes. The impact is evaluated by simulating the spread after node removal.

What is the time complexity of solving this problem?

The time complexity of this problem is O(n^2) due to the graph traversal for each infected node and the simulation of the infection spread. Space complexity is also O(n^2) for storing the graph and infection states.

terminal

Solution

Solution 1: Union-Find

We can use the union-find data structure to merge all nodes that are not in $initial$ and satisfy $graph[i][j] = 1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

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

Continue Practicing

#924 minimize malware spread #959 regions cut by slashes #839 similar string groups