# Minimize Malware Spread
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimize-malware-spread)
Canonical: https://scaleengineer.com/dsa/problems/minimize-malware-spread
**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:** [DoorDash](https://scaleengineer.com/companies/doordash), [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`.

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**.

Note that if a node was removed from the `initial` list of infected nodes, it might still be infected later due to the malware spread.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

**Input:** graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
**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 directly simulates the outcome for each possible removal. We iterate through every node in the `initial` list, temporarily remove it, and then run a full simulation of the malware spread to see how many nodes get infected. The node whose removal results in the fewest final infections is our answer.
**Time:** O(k * n^2), where `k` is the length of `initial` and `n` is the number of nodes. The outer loop runs `k` times. Inside, the BFS on an adjacency matrix takes O(n^2) time as for each node, we may have to scan its entire row in the matrix. · **Space:** O(n), where `n` is the number of nodes. This space is used for the queue and the `infected` set during the BFS traversal.
**Pros:** Simple to understand and implement.; Directly follows the problem statement's logic.
**Cons:** Highly inefficient due to redundant computations. The entire graph traversal and spread simulation is repeated for each of the `k` nodes in the `initial` list.
### Explanation
The core idea is to test every possibility. For each node `u` in the `initial` set, we consider a scenario where `u` is not initially infected.

We create a new set of initial infections, `initial' = initial - {u}`.

Then, we simulate the spread. A graph traversal algorithm like Breadth-First Search (BFS) is suitable for this. We start a BFS from all nodes in `initial'`.

A `visited` array or set keeps track of all nodes that have become infected. We initialize a queue with the nodes from `initial'` and mark them as visited.

The BFS proceeds as usual: dequeue a node, and for all its unvisited neighbors, mark them as visited and enqueue them.

After the BFS completes, the total number of infected nodes gives us the final count for that scenario.

We repeat this for every node in `initial`, keeping track of the removal that leads to the minimum infection count. If there's a tie, the problem specifies we should choose the node with the smallest index. Sorting the `initial` list beforehand simplifies handling this tie-breaking rule.

```java
import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        Arrays.sort(initial); // Sort for tie-breaking
        
        int minInfectedCount = n + 1;
        int resultNode = -1;
        
        for (int nodeToRemove : initial) {
            Set<Integer> infected = new HashSet<>();
            Queue<Integer> queue = new LinkedList<>();
            
            // Create the new initial set for simulation
            for (int startNode : initial) {
                if (startNode != nodeToRemove) {
                    if (infected.add(startNode)) {
                        queue.add(startNode);
                    }
                }
            }
            
            // Simulate spread with BFS
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v = 0; v < n; v++) {
                    if (graph[u][v] == 1 && !infected.contains(v)) {
                        infected.add(v);
                        queue.add(v);
                    }
                }
            }
            
            if (infected.size() < minInfectedCount) {
                minInfectedCount = infected.size();
                resultNode = nodeToRemove;
            }
        }
        
        return resultNode;
    }
}
```
### Algorithm
- Initialize `min_infected_count` to a value larger than `n` and `result_node` to -1.
- Sort the `initial` array in ascending order. This ensures that if we find multiple nodes that result in the same minimum number of infections, the one with the smallest index is chosen first and retained.
- Iterate through each node `u` in the sorted `initial` list. This `u` is the candidate node to be removed.
- For each `u`, create a new temporary initial set `initial'` which is `initial` without `u`.
- Simulate the malware spread starting from the nodes in `initial'`. A Breadth-First Search (BFS) is a good choice for this simulation.
  - Initialize a queue for the BFS and a `Set` or boolean array `infected` to keep track of all infected nodes.
  - Add all nodes from `initial'` to both the queue and the `infected` set.
  - While the queue is not empty, dequeue a node `curr`. For each of its neighbors `v` (where `graph[curr][v] == 1`), if `v` is not yet infected, mark it as infected and add it to the queue.
- After the simulation (BFS) for `u` is complete, the size of the `infected` set is the total number of infected nodes.
- If this count is less than `min_infected_count`, update `min_infected_count` with the new count and set `result_node = u`.
- After iterating through all nodes in `initial`, `result_node` will hold the answer.

## Optimized Approach using Union-Find and Component Analysis
A more efficient approach involves pre-processing the graph to understand its structure. The key insight is that malware infects entire connected components. By identifying these components first, we can quickly determine the impact of removing an initially infected node without running a full simulation each time. We can use a Union-Find (Disjoint Set Union) data structure to efficiently group nodes into components.
**Time:** O(n^2). Building the DSU structure by iterating through the n x n matrix is the dominant step, taking O(n^2 * α(n)), where α(n) is the nearly constant inverse Ackermann function. The subsequent loops over `initial` are much faster. Thus, the total complexity is effectively O(n^2). · **Space:** O(n). The DSU structure requires O(n) space for the `parent` and `size` arrays. The `infectedCountInComponent` array also takes O(n) space.
**Pros:** Highly efficient. It processes the graph once to find components and then makes decisions quickly.; Avoids redundant simulations, leading to a significantly better time complexity.
**Cons:** Requires knowledge of the Union-Find (Disjoint Set Union) data structure.; The implementation is more complex than the brute-force approach.
### Explanation
First, we model the graph's connected components using a Union-Find data structure. We iterate through the adjacency matrix and for every connection `graph[i][j] == 1`, we `union` nodes `i` and `j`. The Union-Find structure will also maintain the size of each component (the number of nodes in each disjoint set).

After building the components, we analyze the initial infections. We count how many initially infected nodes fall into each component. A map or an array can be used to store this, mapping a component's root to its count of initial infections.

Now, we can evaluate the benefit of removing each node `u` from the `initial` list. The benefit is measured by how many nodes are "saved" from infection.
- If a component contains only **one** initially infected node `u`, removing `u` from the `initial` list saves that entire component from infection. The number of saved nodes is equal to the size of that component.
- If a component contains **more than one** initially infected node, removing just one of them (`u`) won't save the component. The other infected nodes in the same component will still cause the entire component to become infected. In this case, the number of saved nodes is 0.

We iterate through each candidate node `u` in `initial`, calculate its potential "saved" score, and find the node that maximizes this score. If multiple nodes yield the same maximum score, we choose the one with the smallest index, which is handled by sorting `initial` first. If no removal saves any nodes (i.e., all scores are 0), we return the smallest-indexed node from `initial`.

```java
import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        DSU dsu = new DSU(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    dsu.union(i, j);
                }
            }
        }

        int[] infectedCountInComponent = new int[n];
        for (int node : initial) {
            infectedCountInComponent[dsu.find(node)]++;
        }

        Arrays.sort(initial); // Sort for tie-breaking

        int resultNode = initial[0];
        int maxSaved = -1;

        for (int nodeToRemove : initial) {
            int root = dsu.find(nodeToRemove);
            // If this component has only one initial infection, removing it saves the component.
            if (infectedCountInComponent[root] == 1) {
                int componentSize = dsu.size(root);
                if (componentSize > maxSaved) {
                    maxSaved = componentSize;
                    resultNode = nodeToRemove;
                }
            }
        }
        
        return resultNode;
    }

    class DSU {
        private int[] parent;
        private int[] sz; // size of component

        public DSU(int n) {
            parent = new int[n];
            sz = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                sz[i] = 1;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]); // Path compression
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                // Union by size
                if (sz[rootI] < sz[rootJ]) {
                    int temp = rootI;
                    rootI = rootJ;
                    rootJ = temp;
                }
                parent[rootJ] = rootI;
                sz[rootI] += sz[rootJ];
            }
        }
        
        public int size(int i) {
            return sz[find(i)];
        }
    }
}
```
### Algorithm
- **Step 1: Build Components with Union-Find**
  - Create a Union-Find (DSU) data structure for `n` nodes. Initialize each node to be its own parent with a size of 1.
  - Iterate through the `graph` matrix. For every pair of connected nodes `(i, j)` where `graph[i][j] == 1`, perform a `union(i, j)` operation. This merges the sets containing `i` and `j` and updates the component sizes.
- **Step 2: Count Infections per Component**
  - Create an array `infectedCountInComponent` of size `n`, initialized to zeros.
  - Iterate through each `node` in the `initial` list. For each `node`, find its component's root using `dsu.find(node)` and increment the count for that root in `infectedCountInComponent`.
- **Step 3: Find the Best Node to Remove**
  - Sort the `initial` array to handle the tie-breaking rule (smallest index first).
  - Initialize `maxSaved = -1` to track the maximum number of nodes we can save, and `resultNode = initial[0]` as a default answer.
  - Iterate through each `nodeToRemove` in the sorted `initial` list.
    - Find its component's root: `root = dsu.find(nodeToRemove)`.
    - If `infectedCountInComponent[root] == 1`, it means this node is the only source of infection for its entire component. Removing it will save all nodes in this component.
      - The number of saved nodes is `dsu.size(root)`.
      - If this `saved` count is greater than `maxSaved`, update `maxSaved = saved` and `resultNode = nodeToRemove`.
- **Step 4: Return Result**
  - After checking all nodes in `initial`, `resultNode` will hold the node that, when removed, saves the most other nodes. Return `resultNode`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    int[] size = new int[n];
    Arrays.fill(size, 1);
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (graph[i][j] == 1) {
          int pa = find(i), pb = find(j);
          if (pa == pb) {
            continue;
          }
          p[pa] = pb;
          size[pb] += size[pa];
        }
      }
    }
    int mi = Integer.MAX_VALUE;
    int res = initial[0];
    Arrays.sort(initial);
    for (int i = 0; i < initial.length; ++i) {
      int t = 0;
      Set<Integer> s = new HashSet<>();
      for (int j = 0; j < initial.length; ++j) {
        if (i == j) {
          continue;
        }
        if (s.contains(find(initial[j]))) {
          continue;
        }
        s.add(find(initial[j]));
        t += size[find(initial[j])];
      }
      if (mi > t) {
        mi = t;
        res = initial[i];
      }
    }
    return res;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial) {
    int n = graph.size();
    p.resize(n);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    vector<int> size(n, 1);
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (graph[i][j]) {
          int pa = find(i), pb = find(j);
          if (pa == pb)
            continue;
          p[pa] = pb;
          size[pb] += size[pa];
        }
      }
    }
    int mi = 400;
    int res = initial[0];
    sort(initial.begin(), initial.end());
    for (int i = 0; i < initial.size(); ++i) {
      int t = 0;
      unordered_set<int> s;
      for (int j = 0; j < initial.size(); ++j) {
        if (i == j)
          continue;
        if (s.count(find(initial[j])))
          continue;
        s.insert(find(initial[j]));
        t += size[find(initial[j])];
      }
      if (mi > t) {
        mi = t;
        res = initial[i];
      }
    }
    return res;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int: n = len(graph) p = list(range(n)) size = [1] * n def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] for i in range(n): for j in range(i + 1, n): if graph[i][j] == 1: pa, pb = find(i), find(j) if pa == pb: continue p[pa] = pb size[pb] += size[pa] mi = inf res = initial[0] initial . sort() for i in range(len(initial)): t = 0 s = set() for j in range(len(initial)): if i == j: continue if find(initial[j]) in s: continue s . add(find(initial[j])) t += size[find(initial[j])] if mi > t: mi = t res = initial[i] return res

```