Minimize Malware Spread II

Hard
1690.

Minimize Malware Spread II

Minimize Malware Spread II is a hard coding problem on arrays, hash table and depth-first search, asked in Amazon and Google interviews.

A network of n nodes is given as an n x n adjacency matrix graph, where graph[i][j] == 1 means nodes i and j are directly connected.

The nodes in initial start infected by malware. Whenever two directly connected nodes have at least one infected, both become infected; this repeats until no more nodes can be infected. Let M(initial) be the final number of infected nodes.

You may remove exactly one node from initial, deleting it from the network entirely together with all its connections. Return the node whose removal makes M(initial) as small as possible. If several nodes tie, return the one with the smallest index.

Example 1

Input
graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output
0
Explanation
Either removal leaves one infected node; 0 is the smaller index.

Example 2

Input
graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output
1
Explanation
Removing 1 cuts node 2 off from node 0, so only node 0 stays infected.

Example 3

Input
graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output
1

Constraints

  • n == graph.length == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] is 0 or 1
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length < n
  • 0 <= initial[i] <= n - 1
  • all the integers in initial are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function(graph, initial) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize Malware Spread II — Solution in Python, Java & C++

Minimize Malware Spread II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimize Malware Spread II is a hard coding problem on arrays, hash table and depth-first search, asked in Amazon and Google interviews.

Problem statement

A network of n nodes is given as an n x n adjacency matrix graph, where graph[i][j] == 1 means nodes i and j are directly connected.

The nodes in initial start infected by malware. Whenever two directly connected nodes have at least one infected, both become infected; this repeats until no more nodes can be infected. Let M(initial) be the final number of infected nodes.

You may remove exactly one node from initial, deleting it from the network entirely together with all its connections. Return the node whose removal makes M(initial) as small as possible. If several nodes tie, return the one with the smallest index.

Example 1

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Explanation: Either removal leaves one infected node; 0 is the smaller index.

Example 2

Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1
Explanation: Removing 1 cuts node 2 off from node 0, so only node 0 stays infected.

Example 3

Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1

Constraints

  • n == graph.length == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] is 0 or 1
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length < n
  • 0 <= initial[i] <= n - 1
  • all the integers in initial are unique

Hints for Minimize Malware Spread II

  1. Hint 1

    Removing an infected node u saves exactly the clean nodes that would have been infected only through u.

  2. Hint 2

    For each infected node, search outward through clean nodes only (stop at other infected nodes). Record, for every clean node, which infected sources reach it.

  3. Hint 3

    A clean node reached by exactly one source is credited to that source. Return the source with the most credit, breaking ties by the smallest index.

How to solve Minimize Malware Spread II

Unlike the first version of this problem, the removed node disappears from the graph, so it can no longer act as a bridge. A clean node is saved by removing u exactly when every path from the infection to it passes through u first — that is, when u is the only infected node that reaches it through clean nodes.

Approach

  1. Mark the initial nodes as infected.
  2. For each infected u, run a DFS/BFS from u that moves only into clean nodes. For every clean node v reached, increment count[v] and set source[v] = u.
  3. For each clean node with count[v] == 1, add one to saved[source[v]].
  4. Return the initial node with the largest saved, smallest index on ties.

Why it works

With u deleted, a clean node v still gets infected iff some other infected node w reaches it by a path avoiding u. On such a path, the last infected node reaches v through clean nodes only, and it is not u, so v gets a count from a source other than u. Conversely a clean-only path from w != u survives the deletion. So v is saved iff u is its only clean-path source. Every node in initial stays infected except u itself, which is removed either way, so comparing saved compares M(initial).

Complexity

  • Time — O(k · n^2) with an adjacency matrix, k = initial.length
  • Space — O(n)

Pitfalls

  • The searches must not pass through other infected nodes — they would credit a source with nodes another infection reaches anyway.
  • When every node's saved is 0, the answer is the smallest index in initial, which need not be initial[0].
  • This is not LC 924: there the removed node stays in the graph and can still spread malware from neighbours.

Reference solution

Python

from typing import List

def minMalwareSpread(graph: List[List[int]], initial: List[int]) -> int:
    n = len(graph)
    infected = [False] * n
    for u in initial:
        infected[u] = True
    count = [0] * n
    source = [-1] * n
    for u in initial:
        seen = [False] * n
        stack = [u]
        seen[u] = True
        while stack:
            x = stack.pop()
            row = graph[x]
            for v in range(n):
                if row[v] and not seen[v] and not infected[v]:
                    seen[v] = True
                    count[v] += 1
                    source[v] = u
                    stack.append(v)
    saved = [0] * n
    for v in range(n):
        if count[v] == 1:
            saved[source[v]] += 1
    best = -1
    for u in sorted(initial):
        if best == -1 or saved[u] > saved[best]:
            best = u
    return best

Java

public static int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    boolean[] infected = new boolean[n];
    for (int u : initial) infected[u] = true;
    int[] count = new int[n], source = new int[n], saved = new int[n], stack = new int[n];
    for (int u : initial) {
        boolean[] seen = new boolean[n];
        seen[u] = true;
        int top = 0;
        stack[top++] = u;
        while (top > 0) {
            int x = stack[--top];
            for (int v = 0; v < n; v++) {
                if (graph[x][v] == 1 && !seen[v] && !infected[v]) {
                    seen[v] = true; count[v]++; source[v] = u; stack[top++] = v;
                }
            }
        }
    }
    for (int v = 0; v < n; v++) if (count[v] == 1) saved[source[v]]++;
    int best = -1;
    for (int u : initial)
        if (best == -1 || saved[u] > saved[best] || (saved[u] == saved[best] && u < best)) best = u;
    return best;
}

C++

int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
    int n = graph.size();
    vector<bool> infected(n, false);
    for (int u : initial) infected[u] = true;
    vector<int> count(n, 0), source(n, -1), saved(n, 0);
    for (int u : initial) {
        vector<bool> seen(n, false);
        seen[u] = true;
        vector<int> st{u};
        while (!st.empty()) {
            int x = st.back(); st.pop_back();
            for (int v = 0; v < n; v++) {
                if (graph[x][v] == 1 && !seen[v] && !infected[v]) {
                    seen[v] = true; count[v]++; source[v] = u; st.push_back(v);
                }
            }
        }
    }
    for (int v = 0; v < n; v++) if (count[v] == 1) saved[source[v]]++;
    int best = -1;
    for (int u : initial)
        if (best == -1 || saved[u] > saved[best] || (saved[u] == saved[best] && u < best)) best = u;
    return best;
}

JavaScript

var minMalwareSpread = function(graph, initial) {
    var n = graph.length, infected = [], count = [], source = [], saved = [];
    for (var i = 0; i < n; i++) { infected.push(false); count.push(0); source.push(-1); saved.push(0); }
    for (var a = 0; a < initial.length; a++) infected[initial[a]] = true;
    for (var b = 0; b < initial.length; b++) {
        var u = initial[b], seen = [];
        for (var s = 0; s < n; s++) seen.push(false);
        seen[u] = true;
        var stack = [u];
        while (stack.length) {
            var x = stack.pop();
            for (var v = 0; v < n; v++) {
                if (graph[x][v] === 1 && !seen[v] && !infected[v]) {
                    seen[v] = true; count[v]++; source[v] = u; stack.push(v);
                }
            }
        }
    }
    for (var w = 0; w < n; w++) if (count[w] === 1) saved[source[w]]++;
    var best = -1;
    for (var c = 0; c < initial.length; c++) {
        var node = initial[c];
        if (best === -1 || saved[node] > saved[best] || (saved[node] === saved[best] && node < best)) best = node;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets