O(n^2) solution | Clean code with comments
Complexity\n- Time complexity: O(n^2)\n- Space complexity: O(n)\n\n# Code\n\nclass Solution {\n    \n    int[][] graph;\n\n    \n    private static final int ST
# Complexity\n- Time complexity: $$O(n^2)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\n    \n    int[][] graph;\n\n    \n    private static final int STATUS_NOT_VISITED = 0;\n    private static final int STATUS_VISITED = 1;\n    private static final int STATUS_INITIALLY_INFECTED = 3;\n    int[] nodesStatus;\n    \n    int[] initial;\n\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        this.graph = graph;\n        this.initial = initial;\n        this.nodesStatus = new int[graph.length];\n        List<NodesGroup> groups = new ArrayList<>();                \n\n        // iterate over initially infected nodes and mark them in "nodesStatus" structure\n        // Time complexity: O(n)\n        for (int infectedNode : initial) {\n            nodesStatus[infectedNode] = STATUS_INITIALLY_INFECTED;\n        }\n        \n        // iterate over graph and create groups\n        // Time complexity: O(n^2)\n        for (int nodeIndex = 0; nodeIndex < graph.length; nodeIndex++) {\n            if (nodesStatus[nodeIndex] != STATUS_NOT_VISITED) {\n                continue;\n            }\n            NodesGroup group = new NodesGroup();\n            dfs(group, nodeIndex);\n            groups.add(group);\n        }\n    \n        // iterate over groups and check which one:\n        // - can be saved by removing one infected node\n        // - and remember how many nodes are saved by removing this node\n        // Time complexity: O(n)\n        int[] savedNodes = new int[graph.length];\n        for (NodesGroup group : groups) {\n            // important condition: we can save group which is connected with only one infected node\n            if (group.infectedNeighbours.size() == 1) { \n                savedNodes[group.getFirstInfectedNeighbour()] += group.healthyNodes.size();\n            }\n        }\n\n        // We have structure "savedNodes" which aggregates how many nodes can be saved\n        // Time complexity: O(n)\n        Integer nodeThatShouldBeRemoved = getLowestInfectedNode(); // <- default value\n        Integer numberOfNodesThatWillBeSaved = 0;\n        for (int sn = 0; sn < savedNodes.length; sn++) {\n            if (savedNodes[sn] > numberOfNodesThatWillBeSaved) {\n                nodeThatShouldBeRemoved = sn;\n                numberOfNodesThatWillBeSaved = savedNodes[sn];\n            }\n        }\n\n        // You can uncomment this line to see how exactly this structure looks like\n        // System.out.println("groups: " + groups);\n        return nodeThatShouldBeRemoved;\n    }\n\n    private int getLowestInfectedNode() {\n        int minIndex = initial[0];\n        for (int i = 1; i < initial.length; i++) {\n            minIndex = Math.min(minIndex, initial[i]);\n        }\n        return minIndex;\n    }\n\n    private void dfs(NodesGroup group, int nodeIndex) {\n        if (nodesStatus[nodeIndex] == STATUS_NOT_VISITED) {\n            group.healthyNodes.add(nodeIndex);\n            nodesStatus[nodeIndex] = STATUS_VISITED;            \n            for (int ni = 0; ni < graph.length; ni++) {\n                if (this.graph[nodeIndex][ni] == 1) {\n                    dfs(group, ni);\n                }\n            }        \n        } else if (nodesStatus[nodeIndex] == STATUS_INITIALLY_INFECTED) {\n            group.infectedNeighbours.add(nodeIndex);\n        } else {\n            // the last possible option\n            // nodesStatus[nodeIndex] == STATUS_VISITED so... it was already handled\n        }\n    }\n\n    class NodesGroup {\n        Set<Integer> healthyNodes = new HashSet<>();\n        Set<Integer> infectedNeighbours = new HashSet<>();\n\n        public Integer getFirstInfectedNeighbour() {\n            return infectedNeighbours.iterator().next();\n        }\n\n        public String toString() {\n            StringBuilder sb = new StringBuilder();\n            sb.append("\\n");\n            sb.append("hn: " + healthyNodes.toString());\n            sb.append(" | ");\n            sb.append("in: " + infectedNeighbours.toString());\n            return sb.toString();\n        }        \n    }\n}\n```
['Java']