FastPrep
Problem · Graph

Minimize Malware Spread by Removing a Node

Learn this problem
● MediumAkuna CapitalOA

Problem statement

There are gNodes servers numbered from 1 through gNodes. The parallel arrays gFrom and gTo describe undirected connections: edge i joins gFrom[i] and gTo[i].

The binary array malware describes the initial infection state. Node i + 1 is initially infected exactly when malware[i] == 1.

Before malware spreads, remove exactly one initially infected node and all of its incident connections. Then every infected node repeatedly infects each directly connected non-infected node in the remaining network until no new node can be infected.

Return the label of the removed node that minimizes the total number of infected nodes remaining after propagation. If several removals produce the same minimum, return the smallest node label.

Function

minimizeMalwareSpread(gNodes: int, gFrom: int[], gTo: int[], malware: int[]) → int

Examples

Example 1

gNodes = 9gFrom = [1,2,4,6,7]gTo = [2,3,5,7,8]malware = [0,0,1,0,1,0,0,0,0]return = 3

Nodes 3 and 5 are initially infected. Removing node 3 prevents infection in the component containing nodes 1 and 2, leaving only nodes 4 and 5 infected. Removing node 5 would leave three infected nodes, so the answer is 3.

Example 2

gNodes = 3gFrom = [1,2]gTo = [2,3]malware = [1,0,1]return = 1

Removing either initially infected endpoint leaves two infected nodes after propagation. The tie is resolved in favor of the smaller node label, 1.

Constraints

  • 1 <= gNodes <= 2000
  • gFrom.length == gTo.length
  • Every edge endpoint is between 1 and gNodes.
  • malware.length == gNodes
  • Every value in malware is 0 or 1, and at least one node is initially infected.

More Akuna Capital problems

drafts saved locally
public int minimizeMalwareSpread(int gNodes, int[] gFrom, int[] gTo, int[] malware) {
    // write your code here
}
gNodes9
gFrom[1,2,4,6,7]
gTo[2,3,5,7,8]
malware[0,0,1,0,1,0,0,0,0]
expected3
checking account