Scale Engineer

Minimize Malware Spread

Hard
#0878Time: 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.2 companies
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayHash TableGraph
Companies
DoorDashDropbox

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem