Minimize Malware Spread II

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

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.

1import java.util.*;2 3class Solution {4    public int minMalwareSpread(int[][] graph, int[] initial) {5        Arrays.sort(initial);6        int n = graph.length;7        int minInfected = n + 1;8        int resultNode = -1;9 10        for (int nodeToRemove : initial) {11            Set<Integer> infected = new HashSet<>();12            Queue<Integer> queue = new LinkedList<>();13            14            for (int startNode : initial) {15                if (startNode != nodeToRemove) {16                    infected.add(startNode);17                    queue.add(startNode);18                }19            }20 21            // Using a temporary set to avoid ConcurrentModificationException22            Set<Integer> currentInfected = new HashSet<>(infected);23            while (!queue.isEmpty()) {24                int u = queue.poll();25                for (int v = 0; v < n; v++) {26                    if (graph[u][v] == 1 && v != nodeToRemove && !currentInfected.contains(v)) {27                        currentInfected.add(v);28                        queue.add(v);29                    }30                }31            }32 33            if (currentInfected.size() < minInfected) {34                minInfected = currentInfected.size();35                resultNode = nodeToRemove;36            }37        }38        return resultNode;39    }40}