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.
Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] Output: 0
Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1] Output: 1
Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1] 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.In #928 Minimize Malware Spread II, the goal is to remove exactly one initially infected node so that the final malware spread in the network is minimized. The graph is represented as an adjacency matrix, and infection spreads through connected nodes. A key insight is that removing an infected node only helps if it uniquely infects certain clean components.
First, identify all connected components of clean nodes using DFS or BFS, ignoring the initially infected nodes. Then determine which infected nodes can reach each clean component. If a component is reachable by only one infected node, removing that node prevents the entire component from becoming infected. Count the size of such uniquely infected components for each candidate node.
Select the infected node whose removal saves the largest number of nodes, breaking ties by choosing the smallest index. This graph traversal approach efficiently evaluates infection influence while avoiding redundant exploration. The overall complexity depends on traversing the graph and tracking component influence.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS/BFS with Clean Component Mapping | O(n^2) | O(n) |
| Union-Find for Component Tracking | O(n^2) | O(n) |
Pepcoding
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem reflects common FAANG interview themes involving graphs, connected components, and infection propagation. It tests understanding of BFS/DFS, component analysis, and optimization strategies in graph problems.
Ignoring infected nodes allows us to identify pure clean components that could potentially stay uninfected. If only one infected node can reach a clean component, removing that node protects the entire component. This separation simplifies reasoning about infection spread.
The optimal approach is to analyze how infected nodes influence clean connected components. By identifying components of non-infected nodes and tracking which infected nodes can reach them, you can determine which infected node uniquely spreads malware. Removing the node that uniquely infects the largest component minimizes the total spread.
Graph traversal techniques using DFS or BFS are commonly used, along with arrays or hash maps to track component ownership. Union-Find can also help group clean nodes into components efficiently. These structures make it easier to evaluate which infected nodes influence each component.