0928-minimize-malware-spread-ii.js

/**
 * Minimize Malware Spread II
 * Time Complexity: O(I * N^2)
 * Space Complexity: O(N * I)
 */
var minMalwareSpread = function (graph, initial) {
  const totalNodes = graph.length;
  const infectedSourceLookup = new Set(initial);

  initial.sort((firstElement, secondElement) => firstElement - secondElement);
  const infectedSources = initial;

  const nodeContagionSources = new Array(totalNodes).fill(null).map(() => []);

  for (
    let sourceIterator = 0;
    sourceIterator < infectedSources.length;
    sourceIterator++
  ) {
    const currentSourceCandidate = infectedSources[sourceIterator];
    const currentlyReachableNodes = new Set();
    const exploredNodesDuringBFS = new Set(infectedSourceLookup);

    exploredNodesDuringBFS.delete(currentSourceCandidate);

    const explorationQueue = [currentSourceCandidate];

    while (explorationQueue.length > 0) {
      const processingNode = explorationQueue.shift();
      currentlyReachableNodes.add(processingNode);

      for (
        let adjacentNodeIndex = 0;
        adjacentNodeIndex < totalNodes;
        adjacentNodeIndex++
      ) {
        if (
          graph[processingNode][adjacentNodeIndex] === 1 &&
          !exploredNodesDuringBFS.has(adjacentNodeIndex)
        ) {
          exploredNodesDuringBFS.add(adjacentNodeIndex);
          explorationQueue.push(adjacentNodeIndex);
        }
      }
    }

    for (
      let graphNodeIndex = 0;
      graphNodeIndex < totalNodes;
      graphNodeIndex++
    ) {
      if (
        currentlyReachableNodes.has(graphNodeIndex) &&
        !infectedSourceLookup.has(graphNodeIndex)
      ) {
        nodeContagionSources[graphNodeIndex].push(currentSourceCandidate);
      }
    }
  }

  const potentialSavesPerSource = new Map();
  for (
    let targetNodeIndex = 0;
    targetNodeIndex < totalNodes;
    targetNodeIndex++
  ) {
    if (nodeContagionSources[targetNodeIndex].length === 1) {
      const uniqueSource = nodeContagionSources[targetNodeIndex][0];
      potentialSavesPerSource.set(
        uniqueSource,
        (potentialSavesPerSource.get(uniqueSource) || 0) + 1,
      );
    }
  }

  let maximumNodesPreserved = -1;
  let bestRemovalCandidate = infectedSources[0];

  for (
    let candidateIterator = 0;
    candidateIterator < infectedSources.length;
    candidateIterator++
  ) {
    const currentInitialNode = infectedSources[candidateIterator];
    const nodesSavedByRemoval =
      potentialSavesPerSource.get(currentInitialNode) || 0;

    if (nodesSavedByRemoval > maximumNodesPreserved) {
      maximumNodesPreserved = nodesSavedByRemoval;
      bestRemovalCandidate = currentInitialNode;
    } else if (
      nodesSavedByRemoval === maximumNodesPreserved &&
      currentInitialNode < bestRemovalCandidate
    ) {
      bestRemovalCandidate = currentInitialNode;
    }
  }

  return bestRemovalCandidate;
};