Minimize Malware Spread - Leetcode Solution

Problem Statement:

Given a network with n computers, represented by an array graph, where graph[i] is a list of computers j such that the direct connection between computer i and computer j exists. A computer starts to malfunction and infects other computers on the network when the computer connected to it is already infected. You are given a list of initially infected computers infected that represents the computers initially infected.

Return the minimum number of computers that will be infected with malware on the whole network after it has spread completely.

Example:

Input: n = 3, edges = [[0,1],[1,2]], initial = [0,1] Output: 2 Explanation: infected computer 0 infects computer 1 at time 1. infected computer 1 infects computer 2 at time 2. There are a total of 2 computers that will be infected after the network has spread completely.

Approach:

To solve this problem, we need to consider the following points:

1. Initially infected computers are a good starting point. These computers may induce a chain reaction of infections in the network. Hence, we need to start with them.

2. We need to find the clusters of the connected computers in the network. We can use DFS or BFS for this purpose.

3. We need to keep track of the number of nodes that get infected in each cluster.

4. We need to keep track of the set of the initially infected computers that are a part of the minimal set of infected computers for each cluster.

5. We need to sort the initially infected computers in ascending order. This is important because we need to start with the initially infected computer that has the lowest index.

6. We need to simulate the process of the malware spreading through the network. We start with the initially infected computers, we infect their neighbors and we move on to the next layer of neighbors. We keep doing this until there are no more computers to infect.

7. We need to keep track of the number of infected computers at each step. If the number of infected computers exceeds the minimal number of infected computers for a cluster, we can stop the infection process because it means that we have already found a better solution.

8. We need to repeat the above process for all the clusters and find the minimum number of infected computers for the entire network.

Solution:

Let's start by finding the clusters of connected computers in the network. We can use BFS for this purpose.

BFS Algorithm:

1. Initialize a list of visited computers to be empty.

2. For each computer in the network that has not been visited yet, do the following:

   a. Initialize a queue of computers to be infected with the current computer.

   b. Initialize a set of infected computers to be empty.

   c. While the queue is not empty, do the following:

   i. Dequeue a computer from the queue.

   ii. If the computer is not infected yet, add it to the set of infected computers.

   iii. For each neighbor of the current computer that has not been visited yet, do the following:

     1. Mark the neighbor as visited.
     
     2. If the neighbor is infected, add it to the set of infected computers.
     
     3. Otherwise, add the neighbor to the queue to be infected later.
   

   d. If the set of infected computers is not empty, add it to the list of infected clusters.

3. Return the list of infected clusters.

Python Code for BFS Algorithm:

def bfs(graph, visited, initial): infected_clusters = [] for i in range(len(graph)): if i not in visited: queue = [i] infected_set = set() while queue: curr = queue.pop(0) if curr not in infected_set: infected_set.add(curr) if curr in initial: initial.remove(curr) for neighbor in graph[curr]: if neighbor not in visited: visited.add(neighbor) if neighbor in initial: initial.remove(neighbor) elif neighbor not in infected_set: queue.append(neighbor) if infected_set: infected_clusters.append((len(infected_set), infected_set)) return infected_clusters

Now let's write a function to simulate the process of malware spreading through the network. We need to start with the initially infected computers, we infect their neighbors and we move on to the next layer of neighbors. We keep doing this until there are no more computers to infect.

Python Code for Malware Spreading Algorithm:

def spread_malware(graph, infected_set): infected = set(infected_set) while infected: new_infected = set() for computer in infected: for neighbor in graph[computer]: if neighbor not in infected: new_infected.add(neighbor) if len(new_infected) > 0: infected = infected.union(new_infected) else: break return len(infected)

Now that we have the two algorithms implemented, we can write the main function to solve the problem. We need to iterate over the infected clusters, we need to sort the initially infected computers in ascending order, we need to simulate the process of malware spreading through the network and we need to keep track of the minimal number of infected computers for each cluster.

Python Code for Minimize Malware Spread Problem:

def min_malware_spread(graph, initial): visited = set() clusters = bfs(graph, visited, set(initial)) result = sorted(initial)[0] min_infected = float('inf') for size, cluster in sorted(clusters, reverse=True): cluster = sorted(cluster) for computer in cluster: infected_set = set(clust for clust in clusters if computer in clust[1]) infected_set = set.union(*[clust[1] for clust in infected_set]) infected_set.add(computer) num_infected = spread_malware(graph, infected_set) if num_infected < min_infected: min_infected = num_infected result = computer return result

Time Complexity:

Time complexity of BFS algorithm is O(n), where n is the number of computers. We apply BFS algorithm for each unvisited computer and the summation over all of them gives us O(n). Also, the time complexity of the Malware Spreading algorithm is O(n), where n is the number of computers. We apply the Malware Spreading algorithm once for each cluster of infected computers. The time complexity of the main function is dominated by the BFS and Malware Spreading algorithms, so the overall time complexity is O(n^2).

Space Complexity:

Space complexity of BFS algorithm is O(n), where n is the number of computers. We use a set to keep track of the visited computers and we may add all the computers to it. Also, we keep a set of infected computers for each cluster in the network. The number of clusters can be as large as the number of computers, so the space complexity can be O(n^2). The space complexity of the main function is dominated by the BFS function, so the overall space complexity is O(n^2).

1