# Minimize Malware Spread II
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimize-malware-spread-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimize-malware-spread-ii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, Graph
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox)
---
## Problem
You are given a network of `n` nodes represented as an `n x n` adjacency matrix `graph`, where the `ith` node is directly connected to the `jth` node if `graph[i][j] == 1`.

Some nodes `initial` are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose `M(initial)` is the final number of nodes infected with malware in the entire network after the spread of malware stops.

We will remove **exactly one node** from `initial`, **completely removing it and any connections from this node to any other node**.

Return the node that, if removed, would minimize `M(initial)`. If multiple nodes could be removed to minimize `M(initial)`, return such a node with **the smallest index**.

**Example 1:**

**Input:** graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
**Output:** 0

**Example 2:**

**Input:** graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
**Output:** 1

**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`
* `n == graph[i].length`
* `2 <= n <= 300`
* `graph[i][j]` is `0` or `1`.
* `graph[i][j] == graph[j][i]`
* `graph[i][i] == 1`
* `1 <= initial.length < n`
* `0 <= initial[i] <= n - 1`
* All the integers in `initial` are **unique**.

# Approaches
## Brute-Force Simulation
This approach simulates the malware spread for each possible scenario. We iterate through each initially infected node, hypothetically remove it, and then run a full simulation of the malware spread from the remaining infected nodes. The node whose removal results in the fewest total infected nodes is our answer.
**Time:** O(k * n^2), where `k` is the number of initially infected nodes and `n` is the total number of nodes. For each of the `k` nodes to remove, we perform a BFS on the graph, which takes `O(n^2)` time with an adjacency matrix representation. · **Space:** O(n) to store the `infected` set and the queue for BFS.
**Pros:** Simple to understand and implement.; Directly simulates the process described in the problem.
**Cons:** Inefficient due to repeated computations. The malware spread simulation is run from scratch for each potential node removal.
### Explanation
The core idea is to try removing each node from the `initial` set one by one. For each node `u` in `initial` that we consider removing, we define a new set of infected sources, which is `initial` excluding `u`. We also treat `u` as a removed node from the graph, meaning it cannot be visited or spread malware. We then perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from all the new sources. We count the total number of nodes visited during this traversal. This gives us the final number of infected nodes, `M`, for the scenario where `u` is removed. We keep track of the node `u` that leads to the minimum `M` found so far. To handle ties (multiple nodes giving the same minimum `M`), we should return the one with the smallest index. A simple way to do this is to sort the `initial` array first and then iterate. The first node that yields the minimum `M` will be the answer.

```java
import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        Arrays.sort(initial);
        int n = graph.length;
        int minInfected = n + 1;
        int resultNode = -1;

        for (int nodeToRemove : initial) {
            Set<Integer> infected = new HashSet<>();
            Queue<Integer> queue = new LinkedList<>();
            
            for (int startNode : initial) {
                if (startNode != nodeToRemove) {
                    infected.add(startNode);
                    queue.add(startNode);
                }
            }

            // Using a temporary set to avoid ConcurrentModificationException
            Set<Integer> currentInfected = new HashSet<>(infected);
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v = 0; v < n; v++) {
                    if (graph[u][v] == 1 && v != nodeToRemove && !currentInfected.contains(v)) {
                        currentInfected.add(v);
                        queue.add(v);
                    }
                }
            }

            if (currentInfected.size() < minInfected) {
                minInfected = currentInfected.size();
                resultNode = nodeToRemove;
            }
        }
        return resultNode;
    }
}
```
### Algorithm
- Sort the `initial` array in ascending order. This helps in tie-breaking, as we will find the smallest index first.
- Initialize `minInfectedCount` to a value larger than any possible outcome (e.g., `n + 1`) and `resultNode` to the first element of the sorted `initial` array.
- Iterate through each `nodeToRemove` in the sorted `initial` array.
- For each `nodeToRemove`, simulate the spread:
  - Create a set `infected` and a queue for BFS.
  - Add all nodes from `initial` (except `nodeToRemove`) to both the `infected` set and the queue.
  - Perform a BFS. In each step, for a node `u`, explore its neighbors `v`. If `v` is connected, not the `nodeToRemove`, and not already infected, add it to the `infected` set and the queue.
- After the BFS completes, the size of the `infected` set is the total number of infected nodes for this scenario.
- If this count is less than `minInfectedCount`, update `minInfectedCount` with the new count and `resultNode` to `nodeToRemove`.
- After checking all nodes in `initial`, return `resultNode`.

## Component Analysis of Healthy Nodes
This optimized approach avoids re-computing the spread for each removal. Instead, it first analyzes the graph structure by temporarily removing all initially infected nodes. This leaves a "healthy" graph, which is a collection of connected components. We then determine which initial nodes can infect which components. A component is saved from infection only if its single initial infector is removed. By calculating the total size of components saved by removing each initial node, we can find the best node to remove.
**Time:** O(n^2). Finding components takes `O(n^2)`. Mapping infectors to components takes `O(k * n)`. Calculating saved nodes and finding the best node takes `O(n + k)`. The dominant part is `O(n^2)`. · **Space:** O(n*k) in the worst case for the `componentToInfectors` map. Other data structures like `componentId`, `componentSize`, and `savedCount` take `O(n)` space.
**Pros:** Much more efficient than the brute-force approach for larger graphs.; Avoids redundant computations by analyzing the graph structure once.
**Cons:** More complex to implement, involving multiple steps and data structures.; Higher space complexity compared to the brute-force approach.
### Explanation
The key insight is that the final number of infected nodes depends on which "healthy" components get infected. A healthy component is a connected group of nodes that are not in the `initial` set. The strategy is as follows:
1. **Isolate Healthy Components**: First, we identify the connected components in the graph consisting only of non-initial nodes. We can use DFS or BFS to do this. For each such component, we calculate its size and assign a unique ID.
2. **Map Infectors to Components**: Next, for each healthy component, we identify which nodes from the `initial` set are connected to it. We can build a map where keys are component IDs and values are sets of initial nodes that can infect them.
3. **Calculate Saved Nodes**: A component will be saved from infection if and only if we remove its *only* source of infection. So, we look for components that are connected to exactly one initial node. For each such component, if we remove its single infector, we "save" all nodes in that component. We can maintain an array, say `savedCount`, where `savedCount[u]` stores the total number of nodes that would be saved by removing initial node `u`.
4. **Find the Best Node**: Finally, we iterate through the `initial` nodes. The node `u` that has the maximum `savedCount[u]` is the one that minimizes the final infection count. If there's a tie, we choose the one with the smallest index.
This approach is more efficient because it processes the graph structure once to find components and then uses this information to quickly evaluate the outcome of removing each initial node.

```java
import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        Set<Integer> initialSet = new HashSet<>();
        for (int node : initial) {
            initialSet.add(node);
        }

        // 1. Find components of the graph without initial nodes
        int[] componentId = new int[n];
        Arrays.fill(componentId, -1);
        int[] componentSize = new int[n];
        int cId = 0;
        for (int i = 0; i < n; i++) {
            if (!initialSet.contains(i) && componentId[i] == -1) {
                int size = 0;
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                componentId[i] = cId;
                size++;
                while (!q.isEmpty()) {
                    int u = q.poll();
                    for (int v = 0; v < n; v++) {
                        if (graph[u][v] == 1 && !initialSet.contains(v) && componentId[v] == -1) {
                            componentId[v] = cId;
                            size++;
                            q.add(v);
                        }
                    }
                }
                componentSize[cId] = size;
                cId++;
            }
        }

        // 2. Map components to their initial node infectors
        Map<Integer, Set<Integer>> componentToInfectors = new HashMap<>();
        for (int u : initial) {
            Set<Integer> infectedComponents = new HashSet<>();
            for (int v = 0; v < n; v++) {
                if (graph[u][v] == 1 && !initialSet.contains(v)) {
                    infectedComponents.add(componentId[v]);
                }
            }
            for (int infectedCId : infectedComponents) {
                componentToInfectors.computeIfAbsent(infectedCId, k -> new HashSet<>()).add(u);
            }
        }

        // 3. Calculate how many nodes are saved by removing each initial node
        int[] savedCount = new int[n];
        for (Map.Entry<Integer, Set<Integer>> entry : componentToInfectors.entrySet()) {
            if (entry.getValue().size() == 1) {
                int infector = entry.getValue().iterator().next();
                int cSize = componentSize[entry.getKey()];
                savedCount[infector] += cSize;
            }
        }

        // 4. Find the best node to remove
        Arrays.sort(initial);
        int maxSaved = -1;
        int resultNode = initial[0];
        for (int u : initial) {
            if (savedCount[u] > maxSaved) {
                maxSaved = savedCount[u];
                resultNode = u;
            }
        }
        return resultNode;
    }
}
```
### Algorithm
- Put all nodes from `initial` into a `HashSet` for efficient lookups.
- Find connected components of the graph formed by non-initial nodes. Use DFS/BFS.
  - Maintain a `componentId` array to map each node to its component ID.
  - Maintain a `componentSize` array to store the size of each component.
- Create a map `componentToInfectors` to store the set of initial nodes that are adjacent to each healthy component.
- Iterate through each initial node `u`. For each neighbor `v` of `u` that is not an initial node, find its component ID and add `u` to the set of infectors for that component.
- Initialize a `savedCount` array of size `n` to zeros.
- Iterate through the `componentToInfectors` map. If a component is infected by exactly one initial node `u`, add the size of this component to `savedCount[u]`.
- Sort the `initial` array to handle tie-breaking.
- Find the node `u` in `initial` that has the maximum value in `savedCount[u]`. This is the node to remove. Return this node.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
private
  int[] size;
public
  int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    p = new int[n];
    size = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      size[i] = 1;
    }
    boolean[] clean = new boolean[n];
    Arrays.fill(clean, true);
    for (int i : initial) {
      clean[i] = false;
    }
    for (int i = 0; i < n; ++i) {
      if (!clean[i]) {
        continue;
      }
      for (int j = i + 1; j < n; ++j) {
        if (clean[j] && graph[i][j] == 1) {
          union(i, j);
        }
      }
    }
    int[] cnt = new int[n];
    Map<Integer, Set<Integer>> mp = new HashMap<>();
    for (int i : initial) {
      Set<Integer> s = new HashSet<>();
      for (int j = 0; j < n; ++j) {
        if (clean[j] && graph[i][j] == 1) {
          s.add(find(j));
        }
      }
      for (int root : s) {
        cnt[root] += 1;
      }
      mp.put(i, s);
    }
    int mx = -1;
    int ans = 0;
    for (Map.Entry<Integer, Set<Integer>> entry : mp.entrySet()) {
      int i = entry.getKey();
      int t = 0;
      for (int root : entry.getValue()) {
        if (cnt[root] == 1) {
          t += size[root];
        }
      }
      if (mx < t || (mx == t && i < ans)) {
        mx = t;
        ans = i;
      }
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
private
  void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) {
      size[pb] += size[pa];
      p[pa] = pb;
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  vector<int> size;
  int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial) {
    int n = graph.size();
    p.resize(n);
    size.resize(n);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    fill(size.begin(), size.end(), 1);
    vector<bool> clean(n, true);
    for (int i : initial)
      clean[i] = false;
    for (int i = 0; i < n; ++i) {
      if (!clean[i])
        continue;
      for (int j = i + 1; j < n; ++j)
        if (clean[j] && graph[i][j] == 1)
          merge(i, j);
    }
    vector<int> cnt(n, 0);
    unordered_map<int, unordered_set<int>> mp;
    for (int i : initial) {
      unordered_set<int> s;
      for (int j = 0; j < n; ++j)
        if (clean[j] && graph[i][j] == 1)
          s.insert(find(j));
      for (int e : s)
        ++cnt[e];
      mp[i] = s;
    }
    int mx = -1, ans = 0;
    for (auto &[i, s] : mp) {
      int t = 0;
      for (int root : s)
        if (cnt[root] == 1)
          t += size[root];
      if (mx < t || (mx == t && i < ans)) {
        mx = t;
        ans = i;
      }
    }
    return ans;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
  void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa != pb) {
      size[pb] += size[pa];
      p[pa] = pb;
    }
  }
};

```

### Python

```python
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa != pb: size[pb] += size[pa] p[pa] = pb n = len(graph) p = list(range(n)) size = [1] * n clean = [True] * n for i in initial: clean[i] = False for i in range(n): if not clean[i]: continue for j in range(i + 1, n): if clean[j] and graph[i][j] == 1: union(i, j) cnt = Counter() mp = {} for i in initial: s = {find(j) for j in range(n) if clean[j] and graph[i][j] == 1} for root in s: cnt[root] += 1 mp[i] = s mx, ans = - 1, 0 for i, s in mp . items(): t = sum(size[root] for root in s if cnt[root] == 1) if mx < t or mx == t and i < ans: mx, ans = t, i return ans

```