0924-minimize-malware-spread.js

/**
 * Minimize Malware Spread
 * Time Complexity: O(N^2 * α(N))
 * Space Complexity: O(N)
 */
var minMalwareSpread = function (graphMatrix, initiallyInfected) {
  const totalNetworkNodes = graphMatrix.length;
  const dsuParents = Array.from(
    { length: totalNetworkNodes },
    (_, elementIndex) => elementIndex,
  );
  const componentMemberCounts = new Array(totalNetworkNodes).fill(1);

  function findRepresentative(nodeIdentifier) {
    if (dsuParents[nodeIdentifier] !== nodeIdentifier) {
      dsuParents[nodeIdentifier] = findRepresentative(
        dsuParents[nodeIdentifier],
      );
    }
    return dsuParents[nodeIdentifier];
  }

  function uniteSets(firstNode, secondNode) {
    const rootOfFirst = findRepresentative(firstNode);
    const rootOfSecond = findRepresentative(secondNode);
    if (rootOfFirst !== rootOfSecond) {
      dsuParents[rootOfFirst] = rootOfSecond;
      componentMemberCounts[rootOfSecond] += componentMemberCounts[rootOfFirst];
    }
  }

  for (let nodeOneIndex = 0; nodeOneIndex < totalNetworkNodes; nodeOneIndex++) {
    for (
      let nodeTwoIndex = nodeOneIndex + 1;
      nodeTwoIndex < totalNetworkNodes;
      nodeTwoIndex++
    ) {
      if (graphMatrix[nodeOneIndex][nodeTwoIndex] === 1) {
        uniteSets(nodeOneIndex, nodeTwoIndex);
      }
    }
  }

  let maximumSavedComponentSize = 0;
  let optimalNodeToRemove = Math.min(...initiallyInfected);

  for (const candidateNode of initiallyInfected) {
    const candidateRoot = findRepresentative(candidateNode);
    let infectedCountInThisComponent = 0;

    for (const checkNode of initiallyInfected) {
      if (findRepresentative(checkNode) === candidateRoot) {
        infectedCountInThisComponent++;
      }
    }

    if (infectedCountInThisComponent === 1) {
      const currentComponentActualSize = componentMemberCounts[candidateRoot];
      if (currentComponentActualSize > maximumSavedComponentSize) {
        maximumSavedComponentSize = currentComponentActualSize;
        optimalNodeToRemove = candidateNode;
      } else if (currentComponentActualSize === maximumSavedComponentSize) {
        optimalNodeToRemove = Math.min(optimalNodeToRemove, candidateNode);
      }
    }
  }

  return optimalNodeToRemove;
};