Minimize Malware Spread - Solution & Explanation

Q: Is Minimize Malware Spread easy or hard?

Minimize Malware Spread is categorized as a Hard problem on LeetCode. The difficulty comes from recognizing that malware spreads across entire connected components and translating that insight into a union-find or graph traversal solution.

Q: Minimize Malware Spread Python/Java solution

Typical Python or Java implementations use Union-Find arrays for parent and size tracking. After union operations across the adjacency matrix, compute component sizes and infection counts, then select the infected node whose removal saves the largest component.

Q: How to solve Minimize Malware Spread in O(n)?

Achieving strict O(n) time is not feasible because the graph is given as an n x n adjacency matrix, which requires O(n^2) inspection to read all connections. The optimal practical solution uses Union-Find or DFS/BFS with O(n^2) time and O(n) extra space.

Q: What is the best approach for Minimize Malware Spread?

The most efficient approach groups nodes into connected components using Union-Find. After building components, count how many infected nodes belong to each component and track the component size. If a component has exactly one infected node, removing it prevents the entire component from being infected. The algorithm runs in O(n^2) time because the graph is provided as an adjacency matrix.

Q: Is Minimize Malware Spread asked at Google/Amazon/Meta?

Graph component problems like Minimize Malware Spread appear in interviews at large tech companies including Google, Amazon, and Meta. Variations often test connected component analysis, union-find data structures, and reasoning about infection propagation across graphs.

Q: What data structure is used in Minimize Malware Spread?

The primary data structure is Union-Find (Disjoint Set Union) to group nodes into connected components efficiently. Alternatively, DFS or BFS traversal with a visited array can identify the same components without a disjoint set structure.

Q: What is the time complexity of Minimize Malware Spread?

Both the Union-Find and DFS/BFS approaches run in O(n^2) time. The adjacency matrix requires scanning all pairs of nodes to detect edges, which dominates the complexity. Space complexity is O(n) for storing component information, visited arrays, or union-find parent structures.

HardArray Hash Table Depth-First Search Breadth-First Search24 min readAsked at: Amazon, Microsoft, Salesforce +7

Practice this problem

Problem Statement

You are given a network of n nodes represented as an n x n adjacency matrix graph, where the i^th node is directly connected to the j^th 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.

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.

Note that if a node was removed from the initial list of infected nodes, it might still be infected later due to the malware spread.

Example 1:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

Example 2:

Input: graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0

Example 3:

Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
Output: 1

Constraints:

n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] is 0 or 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
All the integers in initial are unique.

Approach Overview

Problem Overview: You are given an undirected graph represented by an adjacency matrix where some nodes are initially infected with malware. Removing exactly one infected node can stop the spread from that source. The goal is to remove the node that minimizes the total number of infected nodes after the malware spreads through connected components. If multiple choices produce the same result, return the smallest node index.

Approach 1: Union-Find to Segment Components (O(n^2) time, O(n) space)

Treat the graph as a set of connected components. Use a Union Find structure to merge nodes whenever graph[i][j] == 1. After building components, compute the size of each component and count how many initially infected nodes fall inside each component. If a component contains exactly one infected node, removing that node prevents the entire component from being infected. Iterate through the initial list and pick the node whose component has a single infection and the largest component size. If no such component exists, return the smallest index from the initial list. This approach works well because malware spreads only within connected components.

Approach 2: DFS/BFS to Determine Component Infections (O(n^2) time, O(n) space)

Instead of Union-Find, traverse components directly using Depth-First Search or Breadth-First Search. Start from each unvisited node and perform a DFS/BFS to collect all nodes in that component. Track two values during traversal: the component size and how many nodes from initial appear in it. If exactly one infected node exists in the component, removing that node saves the entire component from infection. Maintain the best candidate by comparing saved component sizes and break ties using the smallest node index. This approach avoids the explicit disjoint set structure but still relies on the same core observation about connected components.

Recommended for interviews: The Union-Find approach is usually preferred because it cleanly models connected components and scales well for similar graph problems. Interviewers expect you to recognize that malware spreads across entire components. A DFS/BFS solution shows solid understanding of graph traversal, but Union-Find demonstrates stronger pattern recognition for component grouping problems.

Approach 1: Union-Find to Segment Components

One way to solve the problem is by using the Union-Find algorithm (also known as Disjoint Set Union or DSU) to identify connected components of the graph. Each component can either have one or more initially infected nodes. The objective is to remove a node such that the size of the initially infected nodes is minimized after malware spreads. This approach groups nodes together and calculates the effect of each removal by considering the infection spread of each distinct component.

The solution defines a Union-Find class with find and union methods to manage node groups efficiently. The minMalwareSpread method initiates a Union-Find instance, groups nodes, counts infections per component, sorts initial infections, and finds the best node to remove based on the unique infections that save the most nodes from being infected.

Code

Python C C++Java C#JavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n²) due to graph iteration, where n is the number of nodes. The union-find operations are nearly O(1) on average.
Space Complexity: O(n) for the union-find data structures.

Try this approach in the editor →

Approach 2: DFS/BFS to Determine Component Infections

This approach uses Depth-First Search (DFS) or Breadth-First Search (BFS) to analyze the graph, identify connected components, and determine component-wise infections. The solution calculates how many vertices are infected by each initial node within its component and selects a node for removal that would minimize the spread as much as possible.

This Python code uses BFS to find connected components and tags them. It processes components comparing infection counts and decides which node removal saves the most others from infection. Initial nodes are sorted for minimum index resolution on equal counts.

Code

Python C JavaScript

Python

JavaScript

Complexity

Time Complexity: O(n²) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components.

Try this approach in the editor →

Approach 3: Union Find

According to the problem description, if there are several nodes in the same connected component initially, there can be three situations:

None of these nodes are infected.
Only one node among these nodes is infected.
Multiple nodes among these nodes are infected.

What we need to consider is to minimize the number of infected nodes left after removing a certain infected node.

For situation 1, there are no infected nodes, so we don't need to consider it; for situation 2, only one node is infected, so after removing this node, the other nodes in this connected component will not be infected; for situation 3, multiple nodes are infected, so after removing any infected node, the other nodes in this connected component will still be infected. Therefore, we only need to consider situation 2.

We use a union find set uf to maintain the connectivity of nodes, a variable ans to record the answer, and a variable mx to record the maximum number of infections that can be reduced currently. Initially, ans = n, mx = 0.

Then we traverse the array initial, use a hash table or an array of length n named cnt to count the number of infected nodes in each connected component.

Next, we traverse the array initial again. For each node x, we find the root node root of its connected component. If there is only one infected node in this connected component, i.e., cnt[root] = 1, we update the answer. The update condition is that the number of nodes sz in this connected component is greater than mx or sz equals mx and the value of x is less than ans.

Finally, if ans has not been updated, it means that there are multiple infected nodes in all connected components, so we return the minimum value in initial, otherwise, we return ans.

The time complexity is O(n^2 times \alpha(n)), and the space complexity is O(n). Where n is the number of nodes, and \alpha(n) is the inverse of the Ackermann function.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Union-Find to Segment Components	Time Complexity: O(n²) due to graph iteration, where n is the number of nodes. The union-find operations are nearly O(1) on average. Space Complexity: O(n) for the union-find data structures.
DFS/BFS to Determine Component Infections	Time Complexity: O(n²) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components.
Union Find	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Union-Find to Segment Components	O(n^2)	O(n)	Best general solution for adjacency matrix graphs and component grouping
DFS/BFS Component Traversal	O(n^2)	O(n)	Good when practicing graph traversal without extra data structures

Video Solution

Minimize Malware Spread || Leetcode • Pepcoding • 9,672 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize Malware Spread easy or hard?

Minimize Malware Spread is categorized as a Hard problem on LeetCode. The difficulty comes from recognizing that malware spreads across entire connected components and translating that insight into a union-find or graph traversal solution.

Minimize Malware Spread Python/Java solution

Typical Python or Java implementations use Union-Find arrays for parent and size tracking. After union operations across the adjacency matrix, compute component sizes and infection counts, then select the infected node whose removal saves the largest component.

How to solve Minimize Malware Spread in O(n)?

Achieving strict O(n) time is not feasible because the graph is given as an n x n adjacency matrix, which requires O(n^2) inspection to read all connections. The optimal practical solution uses Union-Find or DFS/BFS with O(n^2) time and O(n) extra space.

What is the best approach for Minimize Malware Spread?

The most efficient approach groups nodes into connected components using Union-Find. After building components, count how many infected nodes belong to each component and track the component size. If a component has exactly one infected node, removing it prevents the entire component from being infected. The algorithm runs in O(n^2) time because the graph is provided as an adjacency matrix.

Is Minimize Malware Spread asked at Google/Amazon/Meta?

Graph component problems like Minimize Malware Spread appear in interviews at large tech companies including Google, Amazon, and Meta. Variations often test connected component analysis, union-find data structures, and reasoning about infection propagation across graphs.

What data structure is used in Minimize Malware Spread?

The primary data structure is Union-Find (Disjoint Set Union) to group nodes into connected components efficiently. Alternatively, DFS or BFS traversal with a visited array can identify the same components without a disjoint set structure.

What is the time complexity of Minimize Malware Spread?

Both the Union-Find and DFS/BFS approaches run in O(n^2) time. The adjacency matrix requires scanning all pairs of nodes to detect edges, which dominates the complexity. Space complexity is O(n) for storing component information, visited arrays, or union-find parent structures.

Ready to solve this problem?

Practice Minimize Malware Spread with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance43.0%

Approaches3

Reading time24 min

Asked at

Amazon Microsoft Salesforce BNY Mellon Uber

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Union-Find to Segment Components

Code

Complexity

Approach 2: DFS/BFS to Determine Component Infections

Code

Complexity

Approach 3: Union Find

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents