Minimize Malware Spread

Leetcode Problem 924: Minimize Malware Spread

Problem Summary

You are given a network of n nodes represented as an n x n adjacency matrix and a list of nodes that are initially infected with malware. Malware spreads through direct connections: whenever two nodes are directly connected and at least one is infected, both become infected. This spreading continues until no more nodes can be infected. You must remove exactly one node from the initial infected list to minimize the total number of infected nodes after the spread completes. Return the node whose removal results in the smallest final infection count. If multiple nodes yield the same minimal spread, return the one with the smallest index. Note that a removed node may still become infected later through the spread. The number of nodes is between 2 and 300.

Techniques

Array
Hash Table
Depth-First Search
Breadth-First Search
Union-Find
Graph Theory

Solution

import { UnionFind } from "../union-find"

function minMalwareSpread(graph: number[][], initial: number[]): number {
    const n = graph.length
    const uf = new UnionFind(n)

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (graph[i][j] === 1) {
                uf.union(i, j)
            }
        }
    }

    const initialSet = new Set(initial)
    const componentSize: number[] = Array(n).fill(0)
    const infected: number[] = Array(n).fill(0)

    for (let i = 0; i < n; i++) {
        const root = uf.find(i)
        componentSize[root]++

        if (initialSet.has(i)) {
            infected[root]++
        }
    }

    initial.sort((a, b) => a - b)

    let result = initial[0]
    let maxSaved = 0

    for (const node of initial) {
        const root = uf.find(node)

        if (infected[root] === 1) {
            if (componentSize[root] > maxSaved) {
                maxSaved = componentSize[root]
                result = node
            }
        }
    }

    return result
}

console.log(minMalwareSpread([[1,1,0],[1,1,0],[0,0,1]], [0,1])) // 0
console.log(minMalwareSpread([[1,0,0],[0,1,0],[0,0,1]], [0,2])) // 0
console.log(minMalwareSpread([[1,1,1],[1,1,1],[1,1,1]], [1,2])) // 1