LeetCode 928: Minimize Malware Spread II Solution

Master LeetCode problem 928 (Minimize Malware Spread II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

928. Minimize Malware Spread II

Hard

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

Problem Explanation

Explanation

To solve this problem, we need to simulate the spread of malware after each initial infected node is removed. For each removal, we count the total number of nodes infected with malware. The node that, when removed, results in the minimum number of infected nodes is the answer.

Create a function dfs to perform depth-first search to mark all nodes that can be infected starting from a given node.
Create a function spread to simulate the spread of malware in the network after removing a specific infected node.
Iterate through each initial infected node, remove it, simulate malware spread, and count the total infected nodes.
Return the node that minimizes the total infected nodes when removed.

Time complexity: O(n^2) - for each initial node, we perform a simulation of malware spread with a complexity of O(n^2). Space complexity: O(n) - for storing infected nodes and visited nodes.

Solution Code

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        // Function to perform depth-first search
        void dfs(int node, Set<Integer> infected, int[] removed) {
            if (infected.contains(node) || removed[node] == 1) return;
            infected.add(node);
            for (int i = 0; i < graph.length; i++) {
                if (graph[node][i] == 1) {
                    dfs(i, infected, removed);
                }
            }
        }
        
        int minNode = initial[0];
        int minCount = Integer.MAX_VALUE;
        for (int i = 0; i < initial.length; i++) {
            int[] removed = new int[graph.length];
            for (int j = 0; j < initial.length; j++) {
                if (j != i) {
                    removed[initial[j]] = 1;
                }
            }
            Set<Integer> infected = new HashSet<>();
            dfs(initial[i], infected, removed);
            if (infected.size() < minCount || (infected.size() == minCount && initial[i] < minNode)) {
                minNode = initial[i];
                minCount = infected.size();
            }
        }
        return minNode;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 928 (Minimize Malware Spread II)?

This page provides optimized solutions for LeetCode problem 928 (Minimize Malware Spread II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 928 (Minimize Malware Spread II)?

The time complexity for LeetCode 928 (Minimize Malware Spread II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 928 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 928 in Java, C++, or Python.

Back to LeetCode Solutions