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.
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.lengthn == graph[i].length2 <= n <= 300graph[i][j] is 0 or 1.graph[i][j] == graph[j][i]graph[i][i] == 11 <= initial.length <= n0 <= initial[i] <= n - 1initial are unique.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.
C
C++
Java
C#
JavaScript
Time Complexity: O(n2) 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.
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.
C
JavaScript
Time Complexity: O(n2) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components.
| Approach | Complexity |
|---|---|
| Union-Find to Segment Components | Time Complexity: O(n2) due to graph iteration, where n is the number of nodes. The union-find operations are nearly O(1) on average. |
| DFS/BFS to Determine Component Infections | Time Complexity: O(n2) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components. |
Minimize Deviation in Array - Leetcode 1675 - Python • NeetCodeIO • 13,081 views views
Watch 9 more video solutions →Practice Minimize Malware Spread with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor