The "Minimize Malware Spread" problem on LeetCode presents you with a network of n nodes, represented as an n x n adjacency matrix called graph. Each node is either clean or initially infected by malware. The list initial contains the indices of infected nodes. Malware spreads from infected nodes to directly connected nodes (in the same connected component).
You can remove exactly one node from initial to minimize the total number of infected nodes after the spread stops. If there are multiple optimal nodes to remove, return the one with the smallest index.
initial are distinct.
Constraints:
1 <= n <= 300
graph.length == n
graph[i][j] is 0 or 1
initial.length >= 1
At first glance, a brute-force approach might be to simulate removing each node in initial and count the resulting spread. However, this would be inefficient for large networks.
To optimize, we recognize that malware only spreads within connected components. If a component contains more than one initially infected node, removing just one won't stop the spread in that component. But if a component contains exactly one infected node, removing it can prevent the entire component from being infected.
So, the key insight is to:
initial, if it is the only infected node in its component, removing it will save all other nodes in the component from infection.initial are present.initial, if it is the only infected node in its component, removing it will save all the other nodes in that component.initial.
This method leverages a hash map for quick component lookups, and sorts initial to handle tie-breaking efficiently.
Input:
graph = [[1,1,0],[1,1,0],[0,0,1]]
initial = [0,1]
Another Example:
graph = [[1,0,0],[0,1,0],[0,0,1]]
initial = [0,2]
class Solution:
def minMalwareSpread(self, graph, initial):
n = len(graph)
colors = [-1] * n
def dfs(node, color):
for nei in range(n):
if graph[node][nei] == 1 and colors[nei] == -1:
colors[nei] = color
dfs(nei, color)
color = 0
for node in range(n):
if colors[node] == -1:
colors[node] = color
dfs(node, color)
color += 1
# Count size of each color/component
size = [0] * color
for c in colors:
size[c] += 1
# Count number of initial nodes in each component
initial_in_color = [0] * color
for node in initial:
initial_in_color[colors[node]] += 1
# Try removing each node in initial
result = float('inf')
max_saved = -1
for node in sorted(initial):
c = colors[node]
if initial_in_color[c] == 1:
if size[c] > max_saved:
max_saved = size[c]
result = node
elif size[c] == max_saved and node < result:
result = node
if result == float('inf'):
result = min(initial)
return result
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
vector<int> colors(n, -1);
int color = 0;
function<void(int, int)> dfs = [&](int node, int c) {
for (int nei = 0; nei < n; ++nei) {
if (graph[node][nei] && colors[nei] == -1) {
colors[nei] = c;
dfs(nei, c);
}
}
};
for (int i = 0; i < n; ++i) {
if (colors[i] == -1) {
colors[i] = color;
dfs(i, color++);
}
}
vector<int> size(color, 0), initial_in_color(color, 0);
for (int i = 0; i < n; ++i) size[colors[i]]++;
for (int node : initial) initial_in_color[colors[node]]++;
sort(initial.begin(), initial.end());
int result = INT_MAX, max_saved = -1;
for (int node : initial) {
int c = colors[node];
if (initial_in_color[c] == 1) {
if (size[c] > max_saved) {
max_saved = size[c];
result = node;
} else if (size[c] == max_saved && node < result) {
result = node;
}
}
}
if (result == INT_MAX) result = *min_element(initial.begin(), initial.end());
return result;
}
};
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
int[] colors = new int[n];
Arrays.fill(colors, -1);
int color = 0;
for (int i = 0; i < n; ++i) {
if (colors[i] == -1) {
dfs(graph, colors, i, color++);
}
}
int[] size = new int[color];
for (int c : colors) size[c]++;
int[] initialInColor = new int[color];
for (int node : initial) initialInColor[colors[node]]++;
Arrays.sort(initial);
int result = Integer.MAX_VALUE, maxSaved = -1;
for (int node : initial) {
int c = colors[node];
if (initialInColor[c] == 1) {
if (size[c] > maxSaved) {
maxSaved = size[c];
result = node;
} else if (size[c] == maxSaved && node < result) {
result = node;
}
}
}
if (result == Integer.MAX_VALUE) result = initial[0];
return result;
}
private void dfs(int[][] graph, int[] colors, int node, int color) {
colors[node] = color;
for (int nei = 0; nei < graph.length; ++nei) {
if (graph[node][nei] == 1 && colors[nei] == -1) {
dfs(graph, colors, nei, color);
}
}
}
}
var minMalwareSpread = function(graph, initial) {
const n = graph.length;
const colors = Array(n).fill(-1);
let color = 0;
function dfs(node, c) {
for (let nei = 0; nei < n; ++nei) {
if (graph[node][nei] && colors[nei] === -1) {
colors[nei] = c;
dfs(nei, c);
}
}
}
for (let i = 0; i < n; ++i) {
if (colors[i] === -1) {
colors[i] = color;
dfs(i, color++);
}
}
const size = Array(color).fill(0);
for (const c of colors) size[c]++;
const initialInColor = Array(color).fill(0);
for (const node of initial) initialInColor[colors[node]]++;
initial.sort((a, b) => a - b);
let result = Infinity, maxSaved = -1;
for (const node of initial) {
const c = colors[node];
if (initialInColor[c] === 1) {
if (size[c] > maxSaved) {
maxSaved = size[c];
result = node;
} else if (size[c] === maxSaved && node < result) {
result = node;
}
}
}
if (result === Infinity) result = Math.min(...initial);
return result;
};
initial, simulate the spread (BFS/DFS) after removing it. This can be O(n^3) in the worst case due to repeated graph traversals.The "Minimize Malware Spread" problem is elegantly solved by leveraging the structure of connected components. By focusing on components with exactly one initial infection, we can efficiently determine which node's removal will maximally reduce the spread. This avoids brute-force simulation and instead uses graph traversal and counting, resulting in a solution that's both efficient and easy to understand.