928. Minimize Malware Spread II

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.

View Leetcode Problem

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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution