Minimize Malware Spread II
Minimize Malware Spread II
You are given a network of n nodes represented as an n x n adjacency matrix graph. The ith node is directly connected to the jth node if graph[i][j] == 1.
Some nodes in the initial list are initially infected by malware. Malware spreads to directly connected nodes if at least one of them is infected. This continues until no more nodes can be infected.
Let M(initial) be the final number of infected nodes.
We will remove exactly one node from the initial list. This removal also eliminates all connections involving that node.
Return the node from initial that, if removed, would minimize M(initial). If there's a tie, return the 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]is0or1.graph[i][j] == graph[j][i]graph[i][i] == 11 <= initial.length < n0 <= initial[i] <= n - 1- All integers in
initialare unique.
Similar LeetCode problem: Minimize Malware Spread II
AI interview prep
Core dilemma
Balancing the immediate reduction in infected nodes by removing a single infected node against the potential for that node to have been a 'bridge' that would have spread malware to a larger component, thus preventing its infection if it were removed.
3 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Minimize Malware Spread II
Minimize Malware Spread II
You are given a network of n nodes represented as an n x n adjacency matrix graph. The ith node is directly connected to the jth node if graph[i][j] == 1.
Some nodes in the initial list are initially infected by malware. Malware spreads to directly connected nodes if at least one of them is infected. This continues until no more nodes can be infected.
Let M(initial) be the final number of infected nodes.
We will remove exactly one node from the initial list. This removal also eliminates all connections involving that node.
Return the node from initial that, if removed, would minimize M(initial). If there's a tie, return the 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]is0or1.graph[i][j] == graph[j][i]graph[i][i] == 11 <= initial.length < n0 <= initial[i] <= n - 1- All integers in
initialare unique.
Similar LeetCode problem: Minimize Malware Spread II