Minimize Malware Spread
Hard · Graphs · Graph · Union Find · Depth-First Search
Problem
A network of n nodes is given as an n x n adjacency matrix graph: graph[i][j] == 1 means nodes i and j are directly connected.
The nodes in initial start out infected. Infection spreads along connections: whenever two directly connected nodes exist and one is infected, the other becomes infected too, until nothing changes. Let M(initial) be the number of infected nodes at the end.
You may take exactly one node out of initial before the spread starts. The node stays in the network, so it can still be infected through its neighbors. Return the node whose removal makes M(initial) smallest. If several nodes give the same result, return the smallest index.
Examples
Input: graph = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]], initial = [2,0] Output: 0
Nodes 0-1 and 2-3 form two components of two, each with one infected node. Removing either saves two nodes, so the smaller index, 0, wins.
Input: graph = [[1,1,1,0],[1,1,1,0],[1,1,1,0],[0,0,0,1]], initial = [1,3] Output: 1
Removing 1 keeps nodes 0-2 clean, so only node 3 ends up infected. Removing 3 still leaves three infected nodes.
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] Output: 0
Both initial nodes share one component: removing either one leaves the other to infect it, so nothing is saved and the smallest index, 0, is returned.
Constraints
- n == graph.length == graph[i].length
- 2 <= n <= 300
- graph[i][j] is 0 or 1
- graph[i][j] == graph[j][i] and graph[i][i] == 1
- 1 <= initial.length <= n
- 0 <= initial[i] <= n - 1
- All values in initial are distinct
Approaches
- Simulate the spread for each choice — time O(k · n²), space O(n)
Follow-up
If the removed node is taken out of the network entirely (with its edges), it can split a component, and the question becomes: for each clean region, how many initial nodes can reach it without passing through another initial node? Run a search from each initial node over the clean nodes and credit regions reached by exactly one of them.
Related problems
Start free on Cariara · Coding problems · System design studio
