0928-minimize-malware-spread-ii.js

/**
 * 928. Minimize Malware Spread II
 * https://leetcode.com/problems/minimize-malware-spread-ii/
 * Difficulty: Hard
 *
 * 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.
 */

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function(graph, initial) {
  const n = graph.length;
  const initialSet = new Set(initial);

  initial.sort((a, b) => a - b);

  const infected = new Set(initial);
  const queue = [...initial];

  for (let i = 0; i < queue.length; i++) {
    const node = queue[i];
    for (let neighbor = 0; neighbor < n; neighbor++) {
      if (graph[node][neighbor] === 1 && !infected.has(neighbor)) {
        infected.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  const sourcesMap = new Array(n).fill().map(() => []);

  for (const initialNode of initial) {
    const reachable = new Set();
    const visited = new Set(initial);
    visited.delete(initialNode);

    const q = [initialNode];
    while (q.length > 0) {
      const node = q.shift();
      reachable.add(node);

      for (let neighbor = 0; neighbor < n; neighbor++) {
        if (graph[node][neighbor] === 1 && !visited.has(neighbor)) {
          visited.add(neighbor);
          q.push(neighbor);
        }
      }
    }

    for (let node = 0; node < n; node++) {
      if (reachable.has(node) && !initialSet.has(node)) {
        sourcesMap[node].push(initialNode);
      }
    }
  }

  const savedCounts = new Map();
  for (let node = 0; node < n; node++) {
    if (sourcesMap[node].length === 1) {
      const source = sourcesMap[node][0];
      savedCounts.set(source, (savedCounts.get(source) || 0) + 1);
    }
  }

  let maxSaved = 0;
  let result = initial[0];

  for (const node of initial) {
    const saved = savedCounts.get(node) || 0;
    if (saved > maxSaved) {
      maxSaved = saved;
      result = node;
    } else if (saved === maxSaved && node < result) {
      result = node;
    }
  }

  return result;
};