Runtime 1 ms Beats 100.00%
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
// Question: Removing means all connections from removed node will be broken but node will stay there and also stay infected.
class Solution {
    int par = 0;
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        boolean[] malware = new boolean[n];
        for (int mal: initial)
            malware[mal] = true;
        int maxHealthy = 0, minMalId = initial[0];
        // TC: O(n * n^2) = O(n^3)
        for (int mal: initial) {
            int count = 0;
            boolean[] vis = new boolean[n];
            vis[mal] = true;
            // if all nodes are visited in 1 call of dfs() for (say to=0) then for to=[1..n]
            // dfs() calls won't happen because of vis[] marked true for those nodes.
            // So, TC of this for() = O(n + n^2) = O(n^2). Refer, Deepak's Graph 2 - 01:01:04.
            for (int to = 0; to < n; to++) {
                if (!vis[to] && graph[mal][to] == 1) {
                    count += dfsHealthy(graph, vis, malware, to);
                }
            }
            // System.out.print(mal + " " + count + " | ");
            if (count > maxHealthy || count == maxHealthy && minMalId > mal) {
                minMalId = mal;
                maxHealthy = count;
            }
        }
        return minMalId;
    }

    // No. of iterations in one dfs = n
    // No. of recursive dfs calls from within = n
    // So, total TC for 1 dfs call from parent method = O(n^2)
    public int dfsHealthy(int[][] graph, boolean[] vis, boolean[] malware, int from) {
        if (malware[from])
            return 0;
        vis[from] = true;
        int count = 0;
        for (int to = 0; to < graph.length; to++) {
            if (!vis[to] && graph[from][to] == 1) {
                int curHealthy = dfsHealthy(graph, vis, malware, to);
                if (curHealthy == 0) {
                    // Marking it false so that later I can visit it again, find it a malware & return 0 to back dfs calls.
                    // If I don't mark false then later I will not enter dfsHealthy() and simply ignore.
                    vis[from] = false;
                    malware[from] = true;
                    return 0;
                }
                count += curHealthy;
            }
        }
        return count + 1;
    }
}
```
['Java']