Minimize Malware Spread II
Asked at Visa
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.
Asked At
| 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).
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.