Minimize Malware Spread

Try to solve the Minimize Malware Spread problem.

We'll cover the following

Statement#

You’re given a network of nn nodes as an n×nn \times n adjacency matrix graph with the ithi^{th} node directly connected to the jthj^{th} node if graph[i][j] == 1.

A list of nodes, initial, is given, which contains nodes initially infected by malware. When two nodes are connected directly and at least one of them is infected by malware, both nodes will be infected by malware. This spread of malware will continue until every node in the connected component of nodes has been infected.

After the infection has stopped spreading, MM will represent the final number of nodes in the entire network that have been infected with malware.

Return a node from initial such that, when this node is removed from the graph, MM is minimized. If multiple nodes can be removed to minimize MM, return the node with the smallest index.

Note: If a node was removed from the initial list of infected nodes, it might still be infected later on due to the malware’s spread.

Constraints:

  • graph.length == graph[i].length
  • 2≤2 \leq n ≤300\leq 300
  • graph[i][j] is 00 or 11.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1≤1 \leq initial.length ≤n\leq n
  • 0≤0 \leq initial[i] ≤n−1\leq n - 1
  • All the integers in the initial are unique.

Examples#

canvasAnimation-image

1 of 2

canvasAnimation-image

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Minimize Malware Spread

1

Given the following graph and the initially infected nodes, which node will help minimize the malware spread?

graph = [[1, 1, 1],
                [1, 1, 0],
                [1, 0, 1]]

initial = [1, 2]

A)

0

B)

1

C)

2

Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Make connected components out of all the connected nodes in the graph through the Union Find algorithm.

Traverse the initial array and store the number of infections in each connected component with an infection in a hash map, infected.

If a connected component from the infected hash map has more than one infected node, ignore it and move to the next iteration of the loop. Otherwise, calculate the size of the component.

Find the component of maximum size that has exactly one infected node.

If there are multiple components of the same size that would count as the largest connected component, choose the one with the smallest index.

Try it yourself#

Implement your solution in main.py in the following coding playground. You will need the provided supporting code to implement your solution.

Python
main.py
union_find.py
Input #1
Input #2
Minimize Malware Spread

Solution: Last Day Where You Can Still Cross

Solution: Minimize Malware Spread