Minimize Malware Spread II — Solution in Python, Java & C++
Minimize Malware Spread II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimize Malware Spread II is a hard coding problem on arrays, hash table and depth-first search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A network of n nodes is given as an n x n adjacency matrix graph, where graph[i][j] == 1 means nodes i and j are directly connected.
The nodes in initial start infected by malware. Whenever two directly connected nodes have at least one infected, both become infected; this repeats until no more nodes can be infected. Let M(initial) be the final number of infected nodes.
You may remove exactly one node from initial, deleting it from the network entirely together with all its connections. Return the node whose removal makes M(initial) as small as possible. If several nodes tie, return the one with the smallest index.
Example 1
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Explanation: Either removal leaves one infected node; 0 is the smaller index.
Example 2
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1
Explanation: Removing 1 cuts node 2 off from node 0, so only node 0 stays infected.
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
Constraints
n == graph.length == graph[i].length2 <= n <= 300graph[i][j] is 0 or 1graph[i][j] == graph[j][i]graph[i][i] == 11 <= initial.length < n0 <= initial[i] <= n - 1all the integers in initial are unique
Hints for Minimize Malware Spread II
Hint 1
Removing an infected node
usaves exactly the clean nodes that would have been infected only throughu.Hint 2
For each infected node, search outward through clean nodes only (stop at other infected nodes). Record, for every clean node, which infected sources reach it.
Hint 3
A clean node reached by exactly one source is credited to that source. Return the source with the most credit, breaking ties by the smallest index.
How to solve Minimize Malware Spread II
Unlike the first version of this problem, the removed node disappears from the graph, so it can no longer act as a bridge. A clean node is saved by removing u exactly when every path from the infection to it passes through u first — that is, when u is the only infected node that reaches it through clean nodes.
Approach
- Mark the initial nodes as infected.
- For each infected
u, run a DFS/BFS fromuthat moves only into clean nodes. For every clean nodevreached, incrementcount[v]and setsource[v] = u. - For each clean node with
count[v] == 1, add one tosaved[source[v]]. - Return the initial node with the largest
saved, smallest index on ties.
Why it works
With u deleted, a clean node v still gets infected iff some other infected node w reaches it by a path avoiding u. On such a path, the last infected node reaches v through clean nodes only, and it is not u, so v gets a count from a source other than u. Conversely a clean-only path from w != u survives the deletion. So v is saved iff u is its only clean-path source. Every node in initial stays infected except u itself, which is removed either way, so comparing saved compares M(initial).
Complexity
- Time —
O(k · n^2) with an adjacency matrix, k = initial.length - Space —
O(n)
Pitfalls
- The searches must not pass through other infected nodes — they would credit a source with nodes another infection reaches anyway.
- When every node's
savedis 0, the answer is the smallest index ininitial, which need not beinitial[0]. - This is not LC 924: there the removed node stays in the graph and can still spread malware from neighbours.
Reference solution
Python
from typing import List
def minMalwareSpread(graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
infected = [False] * n
for u in initial:
infected[u] = True
count = [0] * n
source = [-1] * n
for u in initial:
seen = [False] * n
stack = [u]
seen[u] = True
while stack:
x = stack.pop()
row = graph[x]
for v in range(n):
if row[v] and not seen[v] and not infected[v]:
seen[v] = True
count[v] += 1
source[v] = u
stack.append(v)
saved = [0] * n
for v in range(n):
if count[v] == 1:
saved[source[v]] += 1
best = -1
for u in sorted(initial):
if best == -1 or saved[u] > saved[best]:
best = u
return bestJava
public static int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
boolean[] infected = new boolean[n];
for (int u : initial) infected[u] = true;
int[] count = new int[n], source = new int[n], saved = new int[n], stack = new int[n];
for (int u : initial) {
boolean[] seen = new boolean[n];
seen[u] = true;
int top = 0;
stack[top++] = u;
while (top > 0) {
int x = stack[--top];
for (int v = 0; v < n; v++) {
if (graph[x][v] == 1 && !seen[v] && !infected[v]) {
seen[v] = true; count[v]++; source[v] = u; stack[top++] = v;
}
}
}
}
for (int v = 0; v < n; v++) if (count[v] == 1) saved[source[v]]++;
int best = -1;
for (int u : initial)
if (best == -1 || saved[u] > saved[best] || (saved[u] == saved[best] && u < best)) best = u;
return best;
}C++
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
vector<bool> infected(n, false);
for (int u : initial) infected[u] = true;
vector<int> count(n, 0), source(n, -1), saved(n, 0);
for (int u : initial) {
vector<bool> seen(n, false);
seen[u] = true;
vector<int> st{u};
while (!st.empty()) {
int x = st.back(); st.pop_back();
for (int v = 0; v < n; v++) {
if (graph[x][v] == 1 && !seen[v] && !infected[v]) {
seen[v] = true; count[v]++; source[v] = u; st.push_back(v);
}
}
}
}
for (int v = 0; v < n; v++) if (count[v] == 1) saved[source[v]]++;
int best = -1;
for (int u : initial)
if (best == -1 || saved[u] > saved[best] || (saved[u] == saved[best] && u < best)) best = u;
return best;
}JavaScript
var minMalwareSpread = function(graph, initial) {
var n = graph.length, infected = [], count = [], source = [], saved = [];
for (var i = 0; i < n; i++) { infected.push(false); count.push(0); source.push(-1); saved.push(0); }
for (var a = 0; a < initial.length; a++) infected[initial[a]] = true;
for (var b = 0; b < initial.length; b++) {
var u = initial[b], seen = [];
for (var s = 0; s < n; s++) seen.push(false);
seen[u] = true;
var stack = [u];
while (stack.length) {
var x = stack.pop();
for (var v = 0; v < n; v++) {
if (graph[x][v] === 1 && !seen[v] && !infected[v]) {
seen[v] = true; count[v]++; source[v] = u; stack.push(v);
}
}
}
}
for (var w = 0; w < n; w++) if (count[w] === 1) saved[source[w]]++;
var best = -1;
for (var c = 0; c < initial.length; c++) {
var node = initial[c];
if (best === -1 || saved[node] > saved[best] || (saved[node] === saved[best] && node < best)) best = node;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets