We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Malware Spread II

Difficulty: Hard

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 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.

Key Insights

  • The problem can be modeled using graph traversal techniques (DFS, BFS) to determine how malware spreads through connected components.
  • Removing a node from the initial set will affect the size of the connected component that becomes infected.
  • We need to evaluate the impact of removing each infected node to minimize the total spread of malware.
  • The connected components should be tracked to understand the influence of each node in the spread.

Space and Time Complexity

Time Complexity: O(n^2) - The algorithm primarily involves traversing the graph represented as an adjacency matrix, which takes O(n^2) time.

Space Complexity: O(n) - We utilize additional space for tracking visited nodes and component sizes.

Solution

To solve this problem, we will employ a graph traversal technique to identify connected components of the graph and analyze how the removal of each infected node in the initial set changes the overall spread of malware. We will:

  1. Use DFS or BFS to explore the graph and identify connected components.
  2. For each node in initial, simulate its removal and calculate the resulting number of nodes infected.
  3. Track the minimum number of infected nodes and return the index of the node that achieves this with the smallest index.

Code Solutions

def minimizeMalwareSpread(graph, initial):
    from collections import defaultdict, deque
    
    n = len(graph)
    initial_set = set(initial)
    
    # Finding connected components
    visited = [False] * n
    component = []
    component_id = [-1] * n
    component_size = []
    
    def bfs(start, comp_id):
        q = deque([start])
        size = 0
        while q:
            node = q.popleft()
            if visited[node]:
                continue
            visited[node] = True
            component_id[node] = comp_id
            size += 1
            for neighbor in range(n):
                if graph[node][neighbor] == 1 and not visited[neighbor]:
                    q.append(neighbor)
        return size
    
    for i in range(n):
        if not visited[i]:
            size = bfs(i, len(component))
            component.append(i)
            component_size.append(size)
    
    # Count the malware infections in each component
    malware_count = defaultdict(int)
    for node in initial:
        comp_id = component_id[node]
        malware_count[comp_id] += 1

    min_infected = float('inf')
    result_node = min(initial)
    
    for node in initial:
        comp_id = component_id[node]
        if malware_count[comp_id] == 1:  # This component is solely infected by this node
            infected_count = sum(size for idx, size in enumerate(component_size) if idx != comp_id)
        else:
            infected_count = sum(size for idx, size in enumerate(component_size) if idx != comp_id) + malware_count[comp_id]
        
        if infected_count < min_infected or (infected_count == min_infected and node < result_node):
            min_infected = infected_count
            result_node = node
            
    return result_node
← Back to All Questions