Minimize Malware Spread Ii - Leetcode Solution

Problem Statement:

Given a network consists of m nodes labeled from 0 to m - 1 and an array of edges where edges[i] = [u_i, v_i] represents a directed edge from node u_i to node v_i in the network, and a set initial consisting of nodes we must infect initially.

Return the minimum number of nodes you can infect to reach all nodes in the network. If it is not possible to infect all nodes in the network, return -1.

Approach:

This problem can be viewed as a graph problem, where each node represents a computer in a network, and each edge represents a connection between two computers. The initial set of nodes represents the computers that are infected. The goal is to calculate the minimum number of additional computers that need to be infected to infect all the computers in the network.

The first approach is to use the Breadth-First Search (BFS) algorithm to traverse the graph and find the infected nodes that can be reached from the initial set. The idea is to start from the infected nodes and traverse the graph using BFS until all nodes are infected. If there are some nodes that are not infected, then it means that these nodes are not reachable from the initial set. Therefore, the answer is -1.

The second approach is to use the Union-Find algorithm to find the connected components in the graph. Initially, all nodes are in separate components, and the infected nodes are added to their respective components. Then, we merge the components of nodes that are connected by an edge until all nodes are in the same component. The minimum number of infected nodes needed to infect all nodes in the network is equal to the number of connected components minus the number of infected components.

Implementation:

Approach 1: Breadth-First Search (BFS)

1. Create a set of infected nodes and a queue for BFS.
2. Initialize the infected nodes in the set and add them to the queue.
3. While the queue is not empty, dequeue a node, and add its neighbors to the queue if they are not infected.
4. Mark the dequeued node as infected.
5. If all nodes are infected, return the number of infected nodes, otherwise, return -1.

Here is the Python implementation of the BFS approach:

from collections import deque

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        
        infected = set(initial)
        queue = deque(initial)
        
        while queue:
            node = queue.popleft()
            
            for neighbor, connection in enumerate(graph[node]):
                if connection and neighbor not in infected:
                    infected.add(neighbor)
                    queue.append(neighbor)
                    
        if len(infected) == len(graph):
            return min(initial)
        else:
            return min(initial, key=lambda node: sum(graph[node][i] for i in infected if i != node))

Approach 2: Union-Find Algorithm

1. Create a Union-Find data structure with the number of nodes in the graph.
2. Initialize the infected nodes in the Union-Find data structure.
3. Merge the components associated with the edges that connect the nodes.
4. Count the number of connected components and the number of infected components.
5. Compute the minimum number of infected nodes needed to infect all nodes in the network.

Here is the Python implementation of the Union-Find approach:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = n
        
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    
    def merge(self, i, j):
        i_parent, j_parent = self.find(i), self.find(j)
        if i_parent != j_parent:
            self.parent[i_parent] = j_parent
            self.count -= 1
            
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        
        n = len(graph)
        uf = UnionFind(n)
        
        for i in initial:
            for j in range(n):
                if graph[i][j]:
                    uf.merge(i, j)
                    
        counts = [0]*n
        
        for i in range(n):
            counts[uf.find(i)] += 1
            
        infected_counts = [0]*n
        
        for i in initial:
            infected_counts[uf.find(i)] += 1
            
        max_component_size = max(counts[uf.find(i)] for i in initial)
        
        return min(filter(lambda i: infected_counts[uf.find(i)] == 1 and counts[uf.find(i)] == max_component_size, initial), default=min(initial))

Complexity Analysis:

Approach 1: Breadth-First Search (BFS)

The time complexity of this approach is O(N^2) since the BFS algorithm is called for each node. The space complexity is also O(N^2) since we need to store the graph and the set of infected nodes.

Approach 2: Union-Find Algorithm

The Union-Find algorithm has an amortized time complexity of O(Nα(N)), where α(N) is the inverse Ackermann function, which is almost a constant for all practical values of N. The space complexity is O(N) since we need to store the Union-Find data structure, the graph, and the initial set of infected nodes.

Conclusion:

In this problem, we have discussed two approaches to minimize the malware spread in a network. The first approach uses the Breadth-First Search (BFS) algorithm, which traverses the graph to find the infected nodes that can be reached from the initial set. The second approach uses the Union-Find algorithm to find the connected components in the graph and compute the minimum number of infected nodes needed to infect all nodes in the network. Both approaches have different time and space complexities, and the choice of the approach depends on the size and structure of the graph.

1