Coding Interview PatternsMinimize Malware Spread
HardUnion Find

Minimize Malware Spread

Explanation & Solution

Practice Problem

Description

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, both nodes will be infected. This spread continues until no more nodes can be infected.

Suppose M(initial) is the final number of nodes infected in the entire network after the spread stops. We will remove exactly one node from initial. Return the node that, if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return the one with the smallest index.

Input:graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
0
0
1
1

Output: 0

Explanation: Removing node 0 or 1 prevents 2 nodes from being infected. Return the smaller index.

Constraints

  • n == graph.length == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] is 0 or 1
  • graph[i][i] == 1
  • graph[i][j] == graph[j][i]
  • 1 <= initial.length <= n
  • 0 <= initial[i] <= n - 1
  • All values in initial are unique

Approach

Union Find pattern

1. Build Connected Components

  • Use Union Find to group all connected nodes
  • Track the size of each component during unions

2. Count Infected Nodes per Component

  • For each initially infected node, find its component root
  • Count how many infected nodes are in each component

3. Evaluate Each Infected Node for Removal

  • If a component has exactly 1 infected node, removing it saves the entire component
  • If a component has 2+ infected nodes, removing one still leaves others to spread — saves nothing
  • Track the node whose removal saves the most nodes

4. Handle Ties

  • If multiple nodes save the same amount, return the one with the smallest index
  • Default answer (if no node saves anything) is the smallest index in initial

Key Insight

  • Only components with exactly one infected node benefit from removal — removing the sole infected node saves the whole component
  • Components with multiple infected nodes will be fully infected regardless of which one is removed
Time
O(n²) for building the graph Union Find
Space
O(n)

Visualization

Input:
BFS Traversal3 nodes, 5 edges
012
output—

Press play to start bfs traversal

CurrentQueuedVisited
11 steps

Solution Code

Previous
Making a Large Island
Next
Number of Operations to Make Network Connected