#924

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimize Malware Spread

Identify which single infected node to remove to minimize total malware spread in a connected network graph efficiently.

array hash table depth first search breadth first search union find

Problem Statement

You are given an n x n adjacency matrix graph representing a network of n nodes, where graph[i][j] == 1 indicates a direct connection between nodes i and j, and graph[i][i] == 1 for all i. A subset of nodes, initial, are initially infected by malware, which spreads to all directly connected nodes until no more nodes can be infected.

Define M(initial) as the total number of nodes infected after the malware spread stops. You may remove exactly one node from initial to minimize M(initial). Return the node index whose removal minimizes the final infected count. If multiple nodes yield the same minimized spread, return the node with the smallest index.

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,0,0],[0,1,0],[0,0,1]], initial = [0,2]

Output: 0

Example details omitted.

Example 3

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

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

Use DFS/BFS to Track Infection Spread

Perform a DFS or BFS starting from each initially infected node to identify all nodes each infection can reach. Store the influence count per node to see which nodes are uniquely infected by only one initial node.

Map Unique Infections to Candidates

Use a hash table to map nodes uniquely reachable by a single infected node. Nodes with more unique influence are stronger candidates for removal since eliminating them reduces total malware spread effectively.

Select Optimal Node to Remove

Iterate over initial nodes and calculate the potential reduction in total infections if each is removed. Pick the node with the maximum reduction, breaking ties by smallest index. This ensures the array scanning plus hash lookup pattern is applied efficiently.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(N)

Time complexity is O(N^2) because each node may require scanning all other nodes during DFS/BFS. Space complexity is O(N) to store infection counts and hash mappings for each node.

What Interviewers Usually Probe

Check if you track nodes influenced by multiple infections correctly.
Verify that tie-breaking by node index is implemented consistently.
Confirm that DFS/BFS does not revisit already processed nodes to avoid overcounting.

Common Pitfalls or Variants

Common pitfalls

Confusing total infections with uniquely influenced nodes leads to wrong removal choice.
Failing to handle tie-breaking properly can cause incorrect output.
Overcounting nodes visited by multiple DFS/BFS traversals inflates spread estimates.

Follow-up variants

Consider a variant where multiple nodes can be removed to minimize spread, introducing combinatorial evaluation.
Change adjacency matrix to weighted connections, requiring adjusted spread influence calculation.
Input as adjacency list instead of matrix, which may impact DFS/BFS implementation and performance.

FAQ

What pattern does Minimize Malware Spread emphasize?

This problem focuses on array scanning plus hash lookup to track infection influence across nodes.

Why is DFS or BFS necessary in this problem?

DFS or BFS explores all nodes reachable from each initially infected node, helping calculate which nodes are uniquely infected.

How do I break ties if multiple nodes reduce the same malware count?

Return the node with the smallest index among candidates that achieve the maximum reduction.

Can this approach handle large graphs efficiently?

Yes, using O(N^2) time for adjacency matrix traversal and O(N) space for tracking unique influences works for graphs up to n=300.

What common mistakes should I avoid?

Avoid double-counting nodes infected by multiple sources, mishandling tie-breaking, and confusing total infections with unique influence counts.

terminal

Solution

Solution 1: Union Find

According to the problem description, if there are several nodes in the same connected component initially, there can be three situations:

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

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

Continue Practicing

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