Start by mapping each node to the set of initial infections it can receive using DFS or BFS. Track nodes uniquely influenced by one infection to identify critical candidates. Remove the node whose elimination prevents the largest number of infections, breaking ties by selecting the smallest index.
Problem Statement
You are given an n x n adjacency matrix graph representing a network of n nodes, where graph[i][j] == 1 indicates a direct connection between nodes i and j, and graph[i][i] == 1 for all i. A subset of nodes, initial, are initially infected by malware, which spreads to all directly connected nodes until no more nodes can be infected.
Define M(initial) as the total number of nodes infected after the malware spread stops. You may remove exactly one node from initial to minimize M(initial). Return the node index whose removal minimizes the final infected count. If multiple nodes yield the same minimized spread, return the node with the smallest index.
Examples
Example 1
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Example details omitted.
Example 2
Input: graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0
Example details omitted.
Example 3
Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
Output: 1
Example details omitted.
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.
Solution Approach
Use DFS/BFS to Track Infection Spread
Perform a DFS or BFS starting from each initially infected node to identify all nodes each infection can reach. Store the influence count per node to see which nodes are uniquely infected by only one initial node.
Map Unique Infections to Candidates
Use a hash table to map nodes uniquely reachable by a single infected node. Nodes with more unique influence are stronger candidates for removal since eliminating them reduces total malware spread effectively.
Select Optimal Node to Remove
Iterate over initial nodes and calculate the potential reduction in total infections if each is removed. Pick the node with the maximum reduction, breaking ties by smallest index. This ensures the array scanning plus hash lookup pattern is applied efficiently.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N^2) |
| Space | O(N) |
Time complexity is O(N^2) because each node may require scanning all other nodes during DFS/BFS. Space complexity is O(N) to store infection counts and hash mappings for each node.
What Interviewers Usually Probe
- Check if you track nodes influenced by multiple infections correctly.
- Verify that tie-breaking by node index is implemented consistently.
- Confirm that DFS/BFS does not revisit already processed nodes to avoid overcounting.
Common Pitfalls or Variants
Common pitfalls
- Confusing total infections with uniquely influenced nodes leads to wrong removal choice.
- Failing to handle tie-breaking properly can cause incorrect output.
- Overcounting nodes visited by multiple DFS/BFS traversals inflates spread estimates.
Follow-up variants
- Consider a variant where multiple nodes can be removed to minimize spread, introducing combinatorial evaluation.
- Change adjacency matrix to weighted connections, requiring adjusted spread influence calculation.
- Input as adjacency list instead of matrix, which may impact DFS/BFS implementation and performance.
How GhostInterview Helps
- Automatically maps infection influence per node to identify optimal removal quickly.
- Highlights candidate nodes with unique reach using hash lookups and array scans.
- Ensures tie-breaking and spread counting are accurate for interview-ready solutions.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What pattern does Minimize Malware Spread emphasize?
This problem focuses on array scanning plus hash lookup to track infection influence across nodes.
Why is DFS or BFS necessary in this problem?
DFS or BFS explores all nodes reachable from each initially infected node, helping calculate which nodes are uniquely infected.
How do I break ties if multiple nodes reduce the same malware count?
Return the node with the smallest index among candidates that achieve the maximum reduction.
Can this approach handle large graphs efficiently?
Yes, using O(N^2) time for adjacency matrix traversal and O(N) space for tracking unique influences works for graphs up to n=300.
What common mistakes should I avoid?
Avoid double-counting nodes infected by multiple sources, mishandling tie-breaking, and confusing total infections with unique influence counts.
Need direct help with Minimize Malware Spread instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Minimize Malware Spread from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Minimize Malware Spread II asks to minimize the spread of malware in a network of nodes by removing one infected node.
Open problem page#959 Regions Cut By SlashesDetermine the number of regions in a grid divided by slashes using array scanning and union-find techniques efficiently.
Open problem page#839 Similar String GroupsDetermine the number of connected groups of similar strings by swapping at most two letters using array scanning and hash lookup techniques.
Open problem page