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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Malware Spread

Number: 960

Difficulty: Hard

Paid? No

Companies: DoorDash, Salesforce, TikTok, Dropbox

Problem Description

Given an undirected graph represented as an n x n adjacency matrix, where graph[i][j] = 1 indicates a connection between nodes i and j, some nodes in an initial list are infected with malware. When a node is infected, the malware spreads to all nodes connected to it. You are allowed to remove exactly one node from the initial infected list to potentially reduce the final infected count after the spread stops. Return the node index that minimizes the spread. If there are multiple choices, return the smallest index. Note that even after removal, the node might still become infected if it is connected to other infected nodes.

Key Insights

  • The graph is undirected and fully connected in the sense that if two nodes are in the same connected component, an infection in one will eventually infect all nodes in that component.
  • By removing a node from the initial list, the remaining initially infected nodes will still infect entire connected components.
  • Use connected components detection (via DFS or Union-Find) to group nodes.
  • For each component, count its size and the number of initially infected nodes within it.
  • Only if a component has exactly one initially infected node, removal of that node would save the rest of the component from infection.
  • The final answer is the node whose removal saves the largest number of nodes (largest component size), with ties broken by smallest index. If no such node exists, return the smallest index from the initial list.

Space and Time Complexity

Time Complexity: O(n^2) – We traverse the entire n x n graph to find connected components. Space Complexity: O(n) – We store component information and visited flags for up to n nodes.

Solution

We solve the problem by first using DFS (or Union-Find) to find all connected components in the graph. For each component, we compute its total number of nodes and the count of initially infected nodes. If a component has exactly one initially infected node, then removing that particular node prevents the spread to the rest of the component. We track, for each initially infected node, how many nodes can be saved by its removal (specifically, the component size of its unique component). Finally, we return the candidate with the maximum saving; if no candidate exists (i.e., every component has multiple infections), we return the smallest index from the initial list.

Code Solutions

# Python Implementation

def minMalwareSpread(graph, initial):
    n = len(graph)
    # visited array to track if a node has been processed.
    visited = [False] * n
    # component mapping: node -> component id, and component size mapping.
    comp_id = [-1] * n
    comp_size = {}
    current_component = 0
    
    # DFS function to traverse nodes in the same component.
    def dfs(node):
        stack = [node]
        nodes_in_component = []
        while stack:
            current = stack.pop()
            if not visited[current]:
                visited[current] = True
                comp_id[current] = current_component
                nodes_in_component.append(current)
                # Check all neighbors.
                for neighbor in range(n):
                    if graph[current][neighbor] == 1 and not visited[neighbor]:
                        stack.append(neighbor)
        return nodes_in_component

    # Identify components.
    for i in range(n):
        if not visited[i]:
            nodes = dfs(i)
            comp_size[current_component] = len(nodes)
            current_component += 1

    # Count initial infected nodes in each component.
    init_count = [0] * current_component
    for node in initial:
        init_count[comp_id[node]] += 1

    # Determine the best candidate for removal.
    result = None
    max_saved = -1
    for node in sorted(initial):
        cid = comp_id[node]
        # Only one infected in the component, meaning removal saves component size nodes.
        if init_count[cid] == 1:
            if comp_size[cid] > max_saved:
                max_saved = comp_size[cid]
                result = node

    # If no such node, return the smallest index.
    if result is None:
        result = min(initial)
    return result

# Example usage:
# print(minMalwareSpread([[1,1,0],[1,1,0],[0,0,1]], [0,1]))
← Back to All Questions