928. Minimize Malware Spread II

UnknownView on LeetCode

Array Depth-First Search Breadth-First Search Union Find Matrix

Time: O(n²)

Space: O(n)

Intuition

For each non-initial node, find which initial nodes exclusively reach it. Removing that initial node saves this node.

Algorithm

1BFS from each non-initial node through non-initial nodes to find connected initial nodes.
2If exactly one initial node reaches this non-initial node, removing it saves it.
3Return initial node saving the most non-initial nodes (ties broken by index).

Common Pitfalls

•Nodes reachable from multiple initial nodes cannot be saved by removing one.

928.cs

// Approach: For each initial node, BFS ignoring that node and count nodes reachable only from it; return the node with the highest exclusive reach.
// Time: O(n²) Space: O(n)

public class Solution
{
    public int MinMalwareSpread(int[][] graph, int[] initial)
    {
        int ans = 0;
        int minCount = graph.Length;

        Array.Sort(initial);

        foreach (var i in initial)
        {
            int count = Bfs(graph, i, initial);
            if (count < minCount)
            {
                minCount = count;
                ans = i;
            }
        }

        return ans;
    }

    private int Bfs(int[][] graph, int removed, int[] initial)
    {
        Queue<int> q = new Queue<int>();
        bool[] seen = new bool[graph.Length];
        seen[removed] = true;

        int count = 0;

        foreach (var i in initial)
        {
            if (i != removed)
            {
                q.Enqueue(i);
                seen[i] = true;
            }
        }

        while (q.Count > 0)
        {
            int u = q.Dequeue();
            ++count;
            for (int i = 0; i < graph.Length; ++i)
            {
                if (seen[i])
                    continue;
                if (i != u && graph[i][u] == 1)
                {
                    q.Enqueue(i);
                    seen[i] = true;
                }
            }
        }

        return count;
    }
}

Was this solution helpful?