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 II

Number: 964

Difficulty: Hard

Paid? No

Companies: TikTok, Dropbox

Problem Description

Given an undirected graph represented as an n x n adjacency matrix, some nodes are initially infected by malware. When any infected node is connected to another node, the infection spreads over the connection. You are allowed to remove exactly one node from the initial infected list—this removal deletes the node and all of its connections. The task is to choose a node to remove such that after the malware spread stops, the total number of infected nodes is minimized. In case of multiple optimal answers, return the node with the smallest index.

Key Insights

  • Removing one infected node not only prevents its own infection but also may protect other nodes by breaking infection paths.
  • The spread can be simulated by starting from each remaining infected node (after removal) and propagating using either BFS or DFS.
  • Although advanced union-find or component-based solutions exist, simulating the infection process for each candidate removal is feasible given n <= 300.
  • For each candidate removal, the simulation ignores the removed node completely (both as an infection source and as a neighbor).

Space and Time Complexity

Time Complexity: O(k * n^2) where k is the number of nodes in the initial list (k < n) and n is the number of nodes. In worst-case, this is roughly O(n^3) but acceptable for n up to 300. Space Complexity: O(n) for storing the visited/infected status during simulation.

Solution

We iterate through each node in the initial infected list and simulate the spread of malware after removing that node. For each simulation, we:

  1. Mark the removed candidate as “removed” (i.e., it is not considered in the spread).
  2. Start a BFS/DFS from every remaining initially infected node (skipping the removed one) to compute the final set of infected nodes.
  3. Count how many nodes become infected.
  4. Compare the result to find the candidate removal that minimizes the infection count. In the case of a tie, we select the candidate with the smallest index. This simulation approach uses a graph traversal algorithm (BFS/DFS) for each candidate removal.

Code Solutions

# Python solution with detailed line-by-line comments

from collections import deque

class Solution:
    def minMalwareSpread(self, graph, initial):
        n = len(graph)  # number of nodes in the graph
        initial.sort()   # sort to ensure smallest index is picked in ties
        best_candidate = initial[0]
        min_infected = float('inf')  # keep track of the minimum number of infected nodes
        
        # iterate through every candidate node in initial list
        for candidate in initial:
            infected = [False] * n  # track infection status for each node
            # run BFS for every initially infected node except the candidate removal
            for start in initial:
                if start == candidate:
                    continue  # skip the removed node
                    
                # if starting from a node that is not yet infected, traverse it
                if not infected[start]:
                    queue = deque([start])
                    while queue:
                        node = queue.popleft()
                        # skip if this node is the removed candidate
                        if node == candidate:
                            continue
                        # mark node as infected
                        if not infected[node]:
                            infected[node] = True
                            # try all neighbors of the node
                            for neighbor in range(n):
                                if graph[node][neighbor] == 1 and neighbor != candidate and not infected[neighbor]:
                                    queue.append(neighbor)
            
            # count final infections excluding the removed candidate
            total_infected = sum(1 for i, inf in enumerate(infected) if inf)
            # update answer if this candidate removal yields less infection
            if total_infected < min_infected:
                min_infected = total_infected
                best_candidate = candidate
                
        return best_candidate

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