928. Minimize Malware Spread II
Asked at Visa
Difficulty
Hard
Time
O(k * n^2)
Space
O(n)
Pattern
Array
Companies
1
Problem
You are given a network of n nodes as an n x n adjacency matrix graph. graph[i][j] == 1 means node i and node j are directly connected. Some nodes in the list initial already carry malware.
Malware spreads like this: if two nodes are directly connected and at least one of them is infected, then both become infected. This repeats until nothing new can be infected. Let M(initial) be the total number of infected nodes when the spread stops.
You must remove exactly one node from initial. Removing it deletes the node and every connection it has, so it can no longer be infected and can no longer pass malware along. Return the node whose removal makes M(initial) as small as possible. If several nodes give the same smallest number, return the one with the smallest index.
Removing one infected node cuts its edges
Constraints
- ●
2 <= n <= 300 - ●
n == graph.length == graph[i].length - ●
graph[i][j] is 0 or 1 - ●
graph[i][j] == graph[j][i] (the graph is undirected) - ●
graph[i][i] == 1 - ●
1 <= initial.length < n - ●
0 <= initial[i] <= n - 1 - ●
All values in initial are unique
Examples
graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]0graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]1graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]1Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Visa | Hard | View all Visa questions → |
How to Think About It
Unlike version I, removing the node cuts its edges, so it can also block the spread from other infected nodes that would have passed through it.
Straightforward approach: for each candidate in initial, pretend it is removed and run a BFS from every other initial node, never entering the removed node. Count infected nodes. With n <= 300 this is O(k * n²), which is acceptable.
Smarter approach: for each clean (non-initial) node, find which initial nodes can reach it without passing through another initial node. If exactly one initial node reaches it, removing that initial node saves it. Sum the saved counts per initial node and pick the max.
Tie-breaking: sort initial first and only replace the best answer when the infected count is strictly smaller.
Walkthrough: graph 0-1 connected, 2 isolated, initial [0,1]. Removing 0: 1 still infects only itself -> 1 infected. Removing 1: 0 infects itself -> 1. Tie -> return 0.
Optimal Approach
Step 1: Sort initial; best, bestCount = initial[0], infinity.
Step 2: For each rem in initial:
BFS from every other initial node, skipping rem, over the adjacency matrix.
Let cnt be the number of infected nodes.
If cnt < bestCount: update best and bestCount.
Step 3: Return best.
Time: O(k * n²) where k = len(initial). Space: O(n).
Try each candidate, then BFS
What Trips People Up in Real Interviews
Reusing the version I solution (component sizes). Here removal cuts edges, which changes the components themselves.
Counting the removed node as infected. It is removed from the network entirely.
Breaking ties by input order. The smallest index must win — sort initial or compare explicitly.
Forgetting that the adjacency matrix has 1s on the diagonal; the seen check handles it.
Solution Code
O(k * n^2) timefrom collections import deque
def minMalwareSpread(graph, initial):
n = len(graph)
initial = sorted(initial)
best, best_count = initial[0], float('inf')
for rem in initial:
seen = [False] * n
seen[rem] = True
q = deque()
for s in initial:
if s != rem:
seen[s] = True
q.append(s)
cnt = len(q)
while q:
u = q.popleft()
for v in range(n):
if graph[u][v] and not seen[v]:
seen[v] = True
cnt += 1
q.append(v)
if cnt < best_count:
best, best_count = rem, cnt
return bestFrequently Asked Questions
What is the Minimize Malware Spread II problem?
Minimize Malware Spread II gives you a network (as an adjacency matrix) and a list of initially infected nodes. You may completely remove one infected node — along with all its connections — before malware spreads. Which node should you remove to minimize the final number of infected nodes? Ties go to the smallest index.
How do you solve Minimize Malware Spread II?
The optimal approach runs in O(k * n^2) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimize Malware Spread II?
Minimize Malware Spread II is asked at Visa. It is a hard difficulty problem.
What are common mistakes on Minimize Malware Spread II?
- Reusing the version I solution (component sizes). Here removal cuts edges, which changes the components themselves.
- Counting the removed node as infected. It is removed from the network entirely.
- Breaking ties by input order. The smallest index must win — sort `initial` or compare explicitly.
- Forgetting that the adjacency matrix has 1s on the diagonal; the `seen` check handles it.