LeetCodee

924. Minimize Malware Spread

Jump to Solution: Python Java C++ JavaScript C#

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 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 the initial list.

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,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0

Example 3:

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

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 - 1
All the integers in initial are unique.

Solution

Python Solution

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
            
        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                if size[px] < size[py]:
                    px, py = py, px
                parent[py] = px
                size[px] += size[py]
                
        n = len(graph)
        parent = list(range(n))
        size = [1] * n
        
        # Build the graph
        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j]:
                    union(i, j)
                    
        # Count infected nodes in each component
        infected = [0] * n
        for node in initial:
            infected[find(node)] += 1
            
        # Find the best node to remove
        best_node = min(initial)
        best_size = 0
        
        for node in initial:
            root = find(node)
            if infected[root] == 1 and size[root] > best_size:
                best_size = size[root]
                best_node = node
                
        return best_node

Time Complexity: O(n^2)

We need to process the adjacency matrix and perform union-find operations.

Space Complexity: O(n)

We use arrays to store parent and size information for union-find.

Java Solution

class Solution {
    private int[] parent;
    private int[] size;
    
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        parent = new int[n];
        size = new int[n];
        
        // Initialize parent and size arrays
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        
        // Build the graph
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        
        // Count infected nodes in each component
        int[] infected = new int[n];
        for (int node : initial) {
            infected[find(node)]++;
        }
        
        // Find the best node to remove
        int bestNode = initial[0];
        int bestSize = 0;
        
        for (int node : initial) {
            int root = find(node);
            if (infected[root] == 1 && size[root] > bestSize) {
                bestSize = size[root];
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    private void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            if (size[px] < size[py]) {
                int temp = px;
                px = py;
                py = temp;
            }
            parent[py] = px;
            size[px] += size[py];
        }
    }
}

Time Complexity: O(n^2)

We need to process the adjacency matrix and perform union-find operations.

Space Complexity: O(n)

We use arrays to store parent and size information for union-find.

C++ Solution

class Solution {
private:
    vector parent;
    vector size;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void union_set(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            if (size[px] < size[py]) {
                swap(px, py);
            }
            parent[py] = px;
            size[px] += size[py];
        }
    }
    
public:
    int minMalwareSpread(vector>& graph, vector& initial) {
        int n = graph.size();
        parent.resize(n);
        size.resize(n, 1);
        
        // Initialize parent array
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // Build the graph
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j]) {
                    union_set(i, j);
                }
            }
        }
        
        // Count infected nodes in each component
        vector infected(n, 0);
        for (int node : initial) {
            infected[find(node)]++;
        }
        
        // Find the best node to remove
        int bestNode = initial[0];
        int bestSize = 0;
        
        for (int node : initial) {
            int root = find(node);
            if (infected[root] == 1 && size[root] > bestSize) {
                bestSize = size[root];
                bestNode = node;
            }
        }
        
        return bestNode;
    }
};

Time Complexity: O(n^2)

We need to process the adjacency matrix and perform union-find operations.

Space Complexity: O(n)

We use arrays to store parent and size information for union-find.

JavaScript Solution

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function(graph, initial) {
    const n = graph.length;
    const parent = new Array(n);
    const size = new Array(n).fill(1);
    
    // Initialize parent array
    for (let i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function union(x, y) {
        const px = find(x);
        const py = find(y);
        if (px !== py) {
            if (size[px] < size[py]) {
                [px, py] = [py, px];
            }
            parent[py] = px;
            size[px] += size[py];
        }
    }
    
    // Build the graph
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (graph[i][j]) {
                union(i, j);
            }
        }
    }
    
    // Count infected nodes in each component
    const infected = new Array(n).fill(0);
    for (const node of initial) {
        infected[find(node)]++;
    }
    
    // Find the best node to remove
    let bestNode = initial[0];
    let bestSize = 0;
    
    for (const node of initial) {
        const root = find(node);
        if (infected[root] === 1 && size[root] > bestSize) {
            bestSize = size[root];
            bestNode = node;
        }
    }
    
    return bestNode;
};

Time Complexity: O(n^2)

We need to process the adjacency matrix and perform union-find operations.

Space Complexity: O(n)

We use arrays to store parent and size information for union-find.

C# Solution

public class Solution {
    private int[] parent;
    private int[] size;
    
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        parent = new int[n];
        size = new int[n];
        
        // Initialize parent and size arrays
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        
        // Build the graph
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    Union(i, j);
                }
            }
        }
        
        // Count infected nodes in each component
        int[] infected = new int[n];
        foreach (int node in initial) {
            infected[Find(node)]++;
        }
        
        // Find the best node to remove
        int bestNode = initial[0];
        int bestSize = 0;
        
        foreach (int node in initial) {
            int root = Find(node);
            if (infected[root] == 1 && size[root] > bestSize) {
                bestSize = size[root];
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);
        if (px != py) {
            if (size[px] < size[py]) {
                int temp = px;
                px = py;
                py = temp;
            }
            parent[py] = px;
            size[px] += size[py];
        }
    }
}

Time Complexity: O(n^2)

We need to process the adjacency matrix and perform union-find operations.

Space Complexity: O(n)

We use arrays to store parent and size information for union-find.