928. Minimize Malware Spread II

You are given a network of n nodes represented as an n x n adjacency matrix graph, where the $i^{th}$ node is directly connected to the $j^{th}$ 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.
 

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

From: LeetCode
Link: 928. Minimize Malware Spread II

Solution:

Ideas:

• Try each removal: For every node in the initial array, simulate what happens if we remove it completely from the graph

• Count infections: Use BFS (Breadth-First Search) to spread malware from the remaining initially infected nodes

  • Start from all initial nodes except the removed one
  • Spread through connected nodes
  • Treat the removed node as if it doesn’t exist

• Pick the best: Return the node whose removal results in the fewest total infections

  • If there’s a tie, return the node with the smallest index

Code:

/**
 * Count how many nodes get infected when we remove removedNode 
 * from the graph and start infection from remaining initial nodes.
 */
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;
    
    // Add remaining initial nodes to queue (excluding removedNode)
    for (int i = 0; i < initialSize; i++) {
        if (initial[i] != removedNode) {
            infected[initial[i]] = true;
            queue[rear++] = initial[i];
        }
    }
    
    // BFS to spread infection
    while (front < rear) {
        int node = queue[front++];
        
        // Check all neighbors
        for (int neighbor = 0; neighbor < n; neighbor++) {
            // Skip if not connected, or if it's the removed node, or already infected
            if (graph[node][neighbor] == 0 || neighbor == removedNode || infected[neighbor]) {
                continue;
            }
            
            // Infect the neighbor
            infected[neighbor] = true;
            queue[rear++] = neighbor;
        }
    }
    
    // Count total infected nodes
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (infected[i]) {
            count++;
        }
    }
    
    free(infected);
    free(queue);
    return count;
}

int minMalwareSpread(int** graph, int graphSize, int* graphColSize, int* initial, int initialSize) {
    int n = graphSize;
    int minInfected = n + 1;  // Start with impossible value
    int bestNode = initial[0];
    
    // Find the smallest node in initial (for tie-breaking)
    for (int i = 1; i < initialSize; i++) {
        if (initial[i] < bestNode) {
            bestNode = initial[i];
        }
    }
    
    // Try removing each node in initial and find the best one
    for (int i = 0; i < initialSize; i++) {
        int node = initial[i];
        int infectedCount = countInfected(graph, n, initial, initialSize, node);
        
        // Update if we found a better option (fewer infections)
        // or same infections but smaller index
        if (infectedCount < minInfected) {
            minInfected = infectedCount;
            bestNode = node;
        } else if (infectedCount == minInfected && node < bestNode) {
            bestNode = node;
        }
    }
    
    return bestNode;
}

// Helper function to create a 2D array
int** createGraph(int n, int data[][300]) {
    int** graph = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            graph[i][j] = data[i][j];
        }
    }
    return graph;
}

// Helper function to free graph
void freeGraph(int** graph, int n) {
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
}