924. Minimize Malware Spread - Detailed Explanation

Problem Statement

You are given an undirected graph represented by an n x n adjacency matrix where graph[i][j] = 1 indicates that node i is directly connected to node j (and vice versa, since the graph is undirected). Each node is connected to itself (i.e. graph[i][i] = 1). Also, you are provided with an integer array initial representing the list of nodes that are initially infected with malware.

Malware Spread Process:

• The malware spreads from an infected node to any other node that is directly connected to it.
• The spread continues until no more nodes can be infected.

Your Task:
Remove exactly one node from the initial list. When you remove a node, it is as if that node is completely removed from the network—it cannot infect others, nor can it be infected.
Your goal is to choose the node whose removal minimizes the total number of infected nodes after the spread stops. If multiple nodes yield the same minimized spread, return the node with the smallest index.

Example 1

• Input:

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

• Output: 0
• Explanation:
  The nodes 0 and 1 form a connected component. If we remove node 0, then node 1 remains infected, but node 0 (and the rest of the component) is not affected. Conversely, removing node 1 yields a similar effect. Since both choices save the same number of nodes, we choose the smaller index, which is 0.

Example 2

• Input:

  graph = [
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]
  ]
  initial = [0, 2]
  

• Output: 0
• Explanation:
  Here, there are no connections between any nodes except self-loops. Removing either node will only prevent its own spread. By the rule of returning the smallest index, the answer is 0.

Example 3

• Input:

  graph = [
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1]
  ]
  initial = [1, 2]
  

• Output: 1
• Explanation:
  In a completely connected graph, if there are multiple initial infected nodes in the same connected component, removing one does not help prevent the spread because the other infected node will still infect the entire component. In this case, neither removal offers a reduction in spread, so we return the smallest index among the initial nodes (which is 1).

Constraints

• The number of nodes n is determined by the dimensions of the graph.
• The graph is a square matrix, and all graph[i][j] are either 0 or 1.
• graph[i][j] = graph[j][i] (i.e., the graph is undirected).
• graph[i][i] = 1 for every node i.
• The length of the initial array is between 1 and n.

Hints for the Approach

• Hint 1: Think about the graph in terms of its connected components. How many nodes are in each component? How many initially infected nodes are in each component?
• Hint 2: If a connected component has exactly one initially infected node, then removing that node could save the entire component from infection. On the other hand, if a component has two or more initially infected nodes, removal of one will not stop the infection from spreading within that component.

Approach 1: Brute Force Simulation

Idea

For every node in the initial list:

• Simulate the spread:
  Remove that node (simulate its absence) and then let the malware spread from the remaining initial nodes.
• Count the number of infected nodes.
• Choose the node removal that minimizes the infection.

Drawbacks

• Inefficiency:
  This approach involves simulating the spread multiple times (once for each candidate), which can lead to a high time complexity—especially with a larger number of nodes (potentially (O(n^3))).

Visual Example

Imagine a graph with four nodes:

• Component 1: Nodes 0, 1 (connected)
• Component 2: Nodes 2, 3 (connected)
• If only node 0 is infected in component 1 and node 2 in component 2, then removing node 0 or node 2 saves its corresponding component.
• However, if a component has two infected nodes, removal of one doesn’t prevent the other from infecting the whole component.

Pseudocode

for each node in initial:
    remove the node from the network
    simulate malware spread starting from the remaining initial nodes
    count infected nodes
choose the node that minimizes infection (tie-break by smallest index)

Approach 2: Optimal Using Connected Components

Idea

1. Find Connected Components:
   Use DFS (or Union-Find) to identify each connected component in the graph.

2. Count Infected Nodes per Component:
   For every component, count the total nodes and the number of initially infected nodes.

3. Decide the Removal:

   • If a component has exactly one infected node, removing that node can save the entire component.
   • Calculate the "saved" count (i.e., the number of nodes in the component) if that node is removed.
   • Choose the candidate node that saves the maximum number of nodes.
   • If no candidate saves any nodes (i.e. all components have 2 or more infected nodes), return the smallest index from the initial list.

Visual Walkthrough

Consider the following graph:

graph = [
  [1, 1, 0, 0],
  [1, 1, 0, 0],
  [0, 0, 1, 1],
  [0, 0, 1, 1]
]
initial = [0, 2]

• Step 1: Identify connected components:
  • Component A: Nodes 0 and 1 (size = 2)
  • Component B: Nodes 2 and 3 (size = 2)
• Step 2: Count infections:
  • Component A: Only node 0 is infected.
  • Component B: Only node 2 is infected.
• Step 3: Removing node 0 saves 2 nodes (Component A) and removing node 2 saves 2 nodes (Component B).
  Tie-break by the smallest index → Answer: 0.

Pseudocode

for each node in graph:
    if not visited:
        perform DFS to get all nodes in its connected component

for each connected component:
    count total nodes and number of initially infected nodes

for each node in initial:
    if it is the only infected node in its component:
        compute the number of nodes saved by removing it

if any candidate exists:
    return the one with the maximum saved nodes (tie-break with smallest index)
else:
    return the smallest index in initial

Complexity Analysis

• Brute Force Simulation:

  • Time Complexity: Up to (O(n^3)) in the worst case because for each candidate (up to (n)), a full spread simulation (which can be (O(n^2))) is performed.

  • Space Complexity: (O(n)) for simulation overhead.

• Optimal Connected Components Approach:

  • Time Complexity: (O(n^2)) is needed to scan the entire adjacency matrix to find components, plus additional (O(n)) work for counting and comparing.

  • Space Complexity: (O(n)) for arrays that keep track of visited nodes and component indices.

Python Implementation