TikTok OA Interview Question: Minimize Malware Spread

You are given a network of n nodes represented as an n x n adjacency matrix graph, where graph[i][j] == 1 means the two nodes i and j are connected, and a list of nodes initial that are initially infected by malware.

Malware will spread to connected nodes. M(initial) is the final number of nodes infected with malware after the spread finishes.

Remove exactly one node from initial. The removed node still has the same connections, but it is no longer initially infected. It can still be infected later from other nodes.

Return the node whose removal would minimize M(initial). If multiple nodes can be removed to minimize M(initial), return the node with the smallest value.

Example Input:

graph = [[1,1,1,0,0],
         [1,1,0,0,0],
         [1,0,1,0,0],
         [0,0,0,1,1],
         [0,0,0,1,1]]
initial = [1,3]

Example Output:

1

Explanation:

• If remove 1, then M(initial) = 2 (3 and 4 will be infected).
• If remove 3, then M(initial) = 3 (0, 1, and 2 will be infected).
• Return 1.

This problem is a graph-connected-component analysis task. The key idea is to group nodes into connected components, then count how many initially infected nodes each component contains. Removing a node only helps if it is the sole infected node in its component, because otherwise the malware will still spread within that component. A common solution uses DFS/BFS or Union-Find to compute component sizes and infection counts, then evaluates each initially infected node by how many nodes it can save, breaking ties by the smallest node index.