Minimize Malware Spread II - Practice Coding Problems

Minimize Malware Spread II - 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 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 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, completely removing it and any connections from this node to any other node.

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.

Input & Output

Example 1 — Basic Connected Graph

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

› Output: 0

💡 Note: Nodes 0 and 1 are connected and initially infected. Node 2 is isolated. If we remove node 0, only node 1 remains infected. If we remove node 1, only node 0 remains infected. Both removals result in 1 infected node, so return the smaller index 0.

Example 2 — Chain Connection

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

› Output: 1

💡 Note: Initial nodes 0,1 are connected. If we remove node 0, the malware spreads from node 1 to nodes 2,3 (total 3 infected). If we remove node 1, only node 0 remains infected (total 1 infected). Removing node 1 minimizes infections.

Example 3 — Multiple Components

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

› Output: 0

💡 Note: All nodes are isolated. Removing either node 0 or 2 results in 1 infected node. Return the smaller index 0.

Constraints

n == graph.length == 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 - 1
All integers in initial are unique

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Network with connections and initially infected nodes [0,1]

Analyze Removal Impact

Test removing each infected node to see spread reduction

Choose Optimal

Select node whose removal minimizes total infections

Key Takeaway

🎯 Key Insight: Remove the infected node that uniquely threatens the largest clean component

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The optimal approach uses Union-Find to efficiently identify connected components of clean nodes, then determines which initially infected node, when removed, saves the most nodes from infection. The key insight is that removing a node only helps if it's the sole connection to a clean component. Time: O(n²α(n)), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Component Analysis	O(n²α(n))	O(n)	Use Union-Find to identify connected components and calculate infection spread efficiently
Brute Force Simulation	O(n³)	O(n²)	Try removing each infected node and simulate malware spread to find minimum

Union-Find with Component Analysis — Algorithm Steps

Build Union-Find structure for clean nodes (non-initially infected)
For each component, count how many initially infected nodes can reach it
Find components that are reached by exactly one initially infected node
Remove the initially infected node that saves the most nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Group Components

Union-Find groups clean nodes into components

Map Infections

Identify which infected nodes threaten each component

Calculate Savings

Remove node that saves the most components

Code -

solution.c — C

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

typedef struct {
    int* parent;
    int* size;
    int n;
} UnionFind;

UnionFind* createUF(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->size = (int*)malloc(n * sizeof(int));
    uf->n = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->size[i] = 1;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionNodes(UnionFind* uf, int x, int y) {
    int px = find(uf, x), py = find(uf, y);
    if (px == py) return;
    if (uf->size[px] < uf->size[py]) {
        int temp = px; px = py; py = temp;
    }
    uf->parent[py] = px;
    uf->size[px] += uf->size[py];
}

int getSize(UnionFind* uf, int x) {
    return uf->size[find(uf, x)];
}

int solution(int** graph, int n, int* initial, int initialSize) {
    int* isInitial = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < initialSize; i++) {
        isInitial[initial[i]] = 1;
    }
    
    // Build Union-Find for clean nodes
    UnionFind* uf = createUF(n);
    
    // Connect clean nodes
    for (int i = 0; i < n; i++) {
        if (!isInitial[i]) {
            for (int j = i + 1; j < n; j++) {
                if (!isInitial[j] && graph[i][j] == 1) {
                    unionNodes(uf, i, j);
                }
            }
        }
    }
    
    // Simplified logic for finding best removal
    int bestNode = initial[0];
    int maxSaving = 0;
    
    for (int i = 0; i < initialSize; i++) {
        int currentSaving = 0;
        // Calculate potential saving for removing initial[i]
        for (int cleanNode = 0; cleanNode < n; cleanNode++) {
            if (!isInitial[cleanNode] && graph[initial[i]][cleanNode] == 1) {
                // Check if this is the only initial node connected to this component
                int uniqueConnection = 1;
                for (int j = 0; j < initialSize; j++) {
                    if (j != i && graph[initial[j]][cleanNode] == 1) {
                        uniqueConnection = 0;
                        break;
                    }
                }
                if (uniqueConnection) {
                    currentSaving += getSize(uf, cleanNode);
                }
            }
        }
        
        if (currentSaving > maxSaving || (currentSaving == maxSaving && initial[i] < bestNode)) {
            maxSaving = currentSaving;
            bestNode = initial[i];
        }
    }
    
    free(isInitial);
    free(uf->parent);
    free(uf->size);
    free(uf);
    
    return bestNode;
}

int main() {
    // Simplified test case
    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};
    
    int result = solution(graph, 3, initial, 2);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²α(n))

Union-Find operations with path compression, where α is inverse Ackermann function

⚠ Quadratic Growth

Space Complexity

O(n)

Union-Find parent array and component size tracking

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 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

Union-Find with Component Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler