Minimize Malware Spread - Practice Coding Problems

Minimize Malware Spread - Problem

Array Hash Table Depth-First Search Breadth-First Search Union Find Graph Hard

You are given a network of n nodes represented as an n × n adjacency matrix graph, where the i-th node is directly connected to the j-th node if graph[i][j] == 1.

Some nodes in initial are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network after the spread of malware 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 such a node with the smallest index.

Note: If a node was removed from the initial list of infected nodes, it might still be infected later due to the malware spread.

Input & Output

Example 1 — Basic Network

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

› Output: 0

💡 Note: Nodes 0 and 1 are connected, so removing either still results in both getting infected. Node 2 is isolated. Since both removals give same result, return smaller index 0.

Example 2 — Unique Infection Source

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

› Output: 0

💡 Note: Each node is isolated. Removing node 0 saves that component, removing node 1 saves its component. Both save 1 node, return smaller index 0.

Example 3 — Large Component

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

› Output: 0

💡 Note: All nodes are connected. Removing either 0 or 1 still results in all 3 nodes infected via the remaining initial node. Return smaller index 0.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Network

Graph with connections and initial infected nodes

Malware Spread

Infection spreads through connections

Optimal Removal

Find node removal that minimizes total infection

Key Takeaway

🎯 Key Insight: Find the initial node whose removal saves the most nodes from infection by analyzing connected components

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is to identify which initial node uniquely infects the largest connected component. Use Union-Find to efficiently group nodes into components, then find the initial node whose removal would save the most nodes. Best approach is Union-Find with component analysis. Time: O(n² × α(n)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(k × n²)	O(n²)	Try removing each initial node and simulate malware spread for each case
Union-Find with Component Analysis	O(n² × α(n))	O(n)	Use Union-Find to identify connected components and calculate impact efficiently

Brute Force Simulation — Algorithm Steps

For each node in initial list
Remove that node and simulate spread using DFS
Count total infected nodes
Return node giving minimum infection count

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Remove Node 0

Remove node 0 from initial, simulate spread from node 1

Try Remove Node 1

Remove node 1 from initial, simulate spread from node 0

Compare Results

Choose removal that gives minimum infected count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int countInfected(int** graph, int n, int* initial, int initialSize, int removedNode) {
    bool* infected = (bool*)calloc(n, sizeof(bool));
    int* queue = (int*)malloc(n * sizeof(int));
    int front = 0, rear = 0;
    
    for (int i = 0; i < initialSize; i++) {
        if (initial[i] != removedNode) {
            infected[initial[i]] = true;
            queue[rear++] = initial[i];
        }
    }
    
    while (front < rear) {
        int node = queue[front++];
        for (int neighbor = 0; neighbor < n; neighbor++) {
            if (graph[node][neighbor] == 1 && !infected[neighbor]) {
                infected[neighbor] = true;
                queue[rear++] = neighbor;
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (infected[i]) count++;
    }
    
    free(infected);
    free(queue);
    return count;
}

int solution(int** graph, int n, int* initial, int initialSize) {
    int minInfected = 1000000;
    int bestNode = -1;
    
    for (int i = 0; i < initialSize; i++) {
        int node = initial[i];
        int infectedCount = countInfected(graph, n, initial, initialSize, node);
        if (infectedCount < minInfected || (infectedCount == minInfected && node < bestNode)) {
            minInfected = infectedCount;
            bestNode = node;
        }
    }
    
    return bestNode;
}

int main() {
    // Simplified for demonstration
    int graph_data[3][3] = {{1,1,0},{1,1,0},{0,0,1}};
    int* graph[3];
    for (int i = 0; i < 3; i++) graph[i] = graph_data[i];
    
    int initial[] = {0, 1};
    
    printf("%d\n", solution(graph, 3, initial, 2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n²)

For each of k initial nodes, we do DFS traversal taking O(n²) time

⚠ Quadratic Growth

Space Complexity

O(n²)

Need to copy the graph and maintain visited arrays for DFS

⚠ Quadratic Space

28.4K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler