924. Minimize Malware Spread

At a Glance

Topic: advanced-graphs
Pattern: Union-Find component analysis + counting / tie-breaking
Difficulty: Hard
Companies: Google, Amazon, Palantir, Two Sigma, Pinterest
Frequency: Low
LeetCode: 924

Undirected graph n nodes; initial nodes are infected. One spread round: malware copies only if an infected node has exactly one colored neighbor in that component (problem-specific rule in statement variants—here LeetCode 924: remove one node from initial to minimize final infected count after synchronized propagation in components). Return smallest index removal that minimizes spread.

Recognition Cues

Components matter — infection confined to connected components
Only removal that uniquely saves a component if it is sole infected “seed” in that component
Union-Find or DFS to cluster, then vote by rules

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Simulate each removal — O(|initial| * (n+m)) — slow.
Union-Find counts — map component sizes and infected counts per component — O(n + m + |initial|).

Optimal Solution

Go

func minMalwareSpread(graph [][]int, initial []int) int {
	nodeCount := len(graph)
	parent := make([]int, nodeCount)
	for node := range parent {
		parent[node] = node
	}
	var find func(int) int
	find = func(node int) int {
		for parent[node] != node {
			parent[node] = parent[parent[node]]
			node = parent[node]
		}
		return node
	}
	union := func(left int, right int) {
		leftRoot := find(left)
		rightRoot := find(right)
		if leftRoot == rightRoot {
			return
		}
		parent[rightRoot] = leftRoot
	}
	for row := 0; row < nodeCount; row++ {
		for col := row + 1; col < nodeCount; col++ {
			if graph[row][col] == 1 {
				union(row, col)
			}
		}
	}
	componentSize := map[int]int{}
	infectedCount := map[int]int{}
	for node := 0; node < nodeCount; node++ {
		root := find(node)
		componentSize[root]++
	}
	for _, node := range initial {
		root := find(node)
		infectedCount[root]++
	}
	bestNode := -1
	bestGain := -1
	for _, node := range initial {
		root := find(node)
		if infectedCount[root] == 1 {
			gain := componentSize[root]
			if gain > bestGain || (gain == bestGain && (bestNode == -1 || node < bestNode)) {
				bestGain = gain
				bestNode = node
			}
		}
	}
	if bestNode != -1 {
		return bestNode
	}
	smallest := initial[0]
	for _, node := range initial {
		if node < smallest {
			smallest = node
		}
	}
	return smallest
}

JavaScript

function minMalwareSpread(graph, initial) {
  const nodeCount = graph.length;
  const parent = Array.from({ length: nodeCount }, (_, index) => index);
  function find(node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node]);
    }
    return parent[node];
  }
  function union(left, right) {
    const leftRoot = find(left);
    const rightRoot = find(right);
    if (leftRoot === rightRoot) {
      return;
    }
    parent[rightRoot] = leftRoot;
  }
  for (let row = 0; row < nodeCount; row += 1) {
    for (let col = row + 1; col < nodeCount; col += 1) {
      if (graph[row][col] === 1) {
        union(row, col);
      }
    }
  }
  const componentSize = new Map();
  const infectedCount = new Map();
  for (let node = 0; node < nodeCount; node += 1) {
    const root = find(node);
    componentSize.set(root, (componentSize.get(root) ?? 0) + 1);
  }
  for (const node of initial) {
    const root = find(node);
    infectedCount.set(root, (infectedCount.get(root) ?? 0) + 1);
  }
  let bestNode = -1;
  let bestGain = -1;
  for (const node of initial) {
    const root = find(node);
    if (infectedCount.get(root) === 1) {
      const gain = componentSize.get(root);
      if (gain > bestGain || (gain === bestGain && (bestNode === -1 || node < bestNode))) {
        bestGain = gain;
        bestNode = node;
      }
    }
  }
  if (bestNode !== -1) {
    return bestNode;
  }
  return Math.min(...initial);
}

Walkthrough

Union all edges. For each component, know size and how many initial seeds fall inside. If a component has exactly one infected node, removing that node saves the whole component from staying infected in models where sole infector removal clears the seed — per 924 definition (minimize final infected by deleting one initial node before spread), the winning removal is the unique infector in a component with maximal savable size; ties by smallest index. If every infected component has >=2 seeds, answer is min(initial).

Invariant: Components are disjoint after DSU; tallies per root capture all statistics needed—no graph traversal per candidate removal.

Edge Cases

Star graph with center infected — removal saves leaves depending on exact propagation rule—match statement (924 uses unique-component rule above)
All nodes connected with multiple initial — fallback smallest index
initial sorted or not — algorithm ignores order except tie-break

Pitfalls

Confusing with 928 Minimize Malware Spread II (different objective / removal budget)
Double-counting component size — count nodes once via root map

Variants

928 — remove k edges — higher complexity; greedy heuristics vs search.
Weighted infections — prioritize max saved weight not count.
Temporally staged infection — simulation with BFS rounds.

Mind-Map Tags

#union-find #component-count #malware #tie-break #greedy-on-components