Infinite Grid? DSU & DFS [Modular w/ Diagram]
General Idea\n\n- If the board is huge, we\'d want to avoid traverse it every time to process everything. \n  [My solution will work even if the grid is infinit
**General Idea**\n\n- If the board is huge, we\'d want to avoid traverse it every time to process everything. \n  *[My solution will work even if the grid is infinitely large as long as we are given a list of virus coordinates.]*\n\n- There is a way to do that - *Union Find* - we can traverse the board 1 time to get all the virus\'s group. \nAnd from there, we do multi source DFS **outward from the virus borders** 1 step per loop. \nAny cell visitied will be marked as visited **because there is no reason to traverse inward.**\nThis way, we only traverse the board **at worst 2 times, at best 1 time, and if we are given virus coordinates, it\'d be at best 0 time.**\n\n- In order to know which group the virus is it, we will assign a group ID to them.\nThe root of each virus group is what we will be using to determined the number of walls and clean cells around it.\n</br>\n\n**Some Details**\n- To track the number of clean cells, we use `i*n+j` as the id for `isInfected[i][j]` along with a HashSet.\n\n- Virus Group ID begins at 2 because 0 and 1 are used by `isInfected[][]` already.\n\n- VIRUS (=1) means a pending virus (that is about to get explored) with no group assigned to it.\n\n- Walled virus will not be explored from other alive, spreading virus.\n\n- Do not kill (set to null) any alive virus that is not the root of the group because other groups of virus may union it.\n</br>\n\n**Simulation (Diagram)**\nTake this testcase for example:\n```\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 1, 0, 0]\n[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 1, 0, 0, 0, 1, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]\n[0, 0, 0, 0, 1, 0, 1, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n```\nIt will be processed like so:\n```\nSTART: \n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 2, 0, 0]\n[3, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 4, 0, 0, 0, 5, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 5, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 6, 0]\n[0, 0, 0, 0, 7, 0, 8, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n------------------------------\n\nVirus Group 5 Walled.\n# of Clean Cells: 6\nWalls Gained: 6\nCurrent ans: 6\n\nVirus Group 4 and 3 United.\nVirus Group 8 and 6 United.\nVirus Group 8 and 7 United.\n\nCurrent board: \n[0, 0, 0, 0, 0, 0, 0, 2, 0, 0]\n[3, 0, 0, 0, 0, 0, 2, 2, 2, 0]\n[3, 4, 4, 0, 0, 0, 0, 2, 0, 0]\n[4, 4, 4, 4, 0, 0, 5, 0, 0, 0]\n[0, 0, 4, 0, 0, 0, 5, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 6, 0]\n[0, 0, 0, 0, 7, 0, 8, 8, 6, 6]\n[0, 0, 0, 7, 7, 8, 8, 8, 8, 0]\n[0, 0, 0, 0, 7, 0, 8, 0, 0, 0]\n------------------------------\n\nVirus Group 6 Walled.\n# of Clean Cells: 13\nWalls Gained: 23\nCurrent ans: 29\n\n\nCurrent board: \n[3, 0, 0, 0, 0, 0, 2, 2, 2, 0]\n[3, 3, 3, 0, 0, 2, 2, 2, 2, 2]\n[3, 4, 4, 3, 0, 0, 2, 2, 2, 0]\n[4, 4, 4, 4, 3, 0, 5, 2, 0, 0]\n[3, 3, 4, 3, 0, 0, 5, 0, 0, 0]\n[0, 0, 3, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 6, 0]\n[0, 0, 0, 0, 7, 0, 8, 8, 6, 6]\n[0, 0, 0, 7, 7, 8, 8, 8, 8, 0]\n[0, 0, 0, 0, 7, 0, 8, 0, 0, 0]\n------------------------------\n\nVirus Group 3 Walled.\n# of Clean Cells: 10\nWalls Gained: 16\nCurrent ans: 45\n\n\nCurrent board: \n[3, 0, 0, 0, 0, 2, 2, 2, 2, 2]\n[3, 3, 3, 0, 2, 2, 2, 2, 2, 2]\n[3, 4, 4, 3, 0, 2, 2, 2, 2, 2]\n[4, 4, 4, 4, 3, 0, 5, 2, 2, 0]\n[3, 3, 4, 3, 0, 0, 5, 2, 0, 0]\n[0, 0, 3, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 6, 0]\n[0, 0, 0, 0, 7, 0, 8, 8, 6, 6]\n[0, 0, 0, 7, 7, 8, 8, 8, 8, 0]\n[0, 0, 0, 0, 7, 0, 8, 0, 0, 0]\n------------------------------\n\nVirus Group 2 Walled.\n# of Clean Cells: 7\nWalls Gained: 11\nCurrent ans: 56\n\n\nCurrent board: \n[3, 0, 0, 0, 0, 2, 2, 2, 2, 2]\n[3, 3, 3, 0, 2, 2, 2, 2, 2, 2]\n[3, 4, 4, 3, 0, 2, 2, 2, 2, 2]\n[4, 4, 4, 4, 3, 0, 5, 2, 2, 0]\n[3, 3, 4, 3, 0, 0, 5, 2, 0, 0]\n[0, 0, 3, 0, 0, 0, 0, 0, 0, 0]\n[0, 0, 0, 0, 0, 0, 0, 0, 6, 0]\n[0, 0, 0, 0, 7, 0, 8, 8, 6, 6]\n[0, 0, 0, 7, 7, 8, 8, 8, 8, 0]\n[0, 0, 0, 0, 7, 0, 8, 0, 0, 0]\n------------------------------\nDone\n```\n\nBelow, I use PriorityQueue to make things simple. We can also use a HashSet and track the max element. \nTreeSet, on the other hand, is quite difficult to make it work for this problem.\n```Java\nclass Solution {\n    int m, n;\n    int VIRUS = 1;\n    int ID = 2;\n    public int containVirus(int[][] isInfected) {\n        m = isInfected.length;\n        n = isInfected[0].length;\n        int ans = 0;\n        Comparator<Virus> comp = Comparator.comparingInt(o -> -o.border.size());\n        PriorityQueue<Virus> maxheap = new PriorityQueue<>(comp);\n        for (int i = 0; i < m; i++){\n            for (int j = 0; j < n; j++){\n                if (isInfected[i][j]==VIRUS){ // mark all virus cells as visited and populate all groups\n                    Set<Integer> border = new HashSet<>();\n                    int id = maxheap.size()+ID;\n                    int walls = mark(i, j, id, isInfected, border, null, null);\n                    maxheap.offer(new Virus(id, walls, border));\n                }\n            }\n        }\n\n        Virus[] virus = new Virus[maxheap.size()+ID]; // lookup virus by ID\n        UF uf = new UF(virus.length); // union find\n\n        while(!maxheap.isEmpty()){ // loop until no more virus group\n            Virus killed = maxheap.poll();\n            ans += killed.walls;\n            virus[killed.id]=null; // kill this virus\n            PriorityQueue<Virus> next = new PriorityQueue<>(comp);\n            for (Virus v : maxheap){\n                for (int p : v.border){\n                    isInfected[p/n][p%n]=VIRUS; // new turn starts, all boarders are now virus\n                }\n            }\n            for (Virus v : maxheap){ // populate the next border and wall count, and union virus groups (if any)\n                int walls = 0;\n                Set<Integer> nb = new HashSet<>();\n                for (int p : v.border){\n                    walls += mark(p/n, p%n, v.id, isInfected, nb, uf, virus);\n                }\n                virus[v.id]=new Virus(v.id, walls, nb);\n            }\n            for (int i = ID; i < virus.length; i++){ // let the root of the virus have it all, and reset the rest\n                if (isAliveVirus(i, uf, virus) && !uf.isRoot(i)){\n                    virus[uf.find(i)].walls+=virus[i].walls;\n                    virus[uf.find(i)].border.addAll(virus[i].border);\n                    virus[i] = new Virus(i, 0, new HashSet<>());\n                }\n            }\n            for (int i = ID; i < virus.length; i++){ // enqueue the root virus for the next round.\n                if (isAliveVirus(i, uf, virus) && uf.isRoot(i)){\n                    next.offer(virus[i]);\n                }\n            }\n            maxheap = next;\n        }\n\n        return ans;\n    }\n\n    private boolean isAliveVirus(int id, UF uf, Virus[] virus){\n        return virus[uf.find(id)]!=null;\n    }\n\n    private boolean isVirus(int id){\n        return id >= ID;\n    }\n\n    private boolean isDeadVirus(int id, UF uf, Virus[] virus){\n        return isVirus(id) && !isAliveVirus(id, uf, virus);\n    }\n\n    private int mark(int i, int j, int id, int[][] grid, Set<Integer> border, UF uf, Virus[] virus){\n        if (i < 0 || j < 0 || i == m || j == n || grid[i][j]==id || isDeadVirus(grid[i][j], uf, virus))\n            return 0;\n        if (isVirus(grid[i][j])){ // union another virus group and exit\n            uf.union(grid[i][j], id);\n            return 0;\n        }\n        if (grid[i][j]==0){\n            border.add(i*n+j);\n            return 1;\n        }\n        grid[i][j]=id;\n        return mark(i+1, j, id, grid, border, uf, virus)\n            +  mark(i-1, j, id, grid, border, uf, virus)\n            +  mark(i, j+1, id, grid, border, uf, virus)\n            +  mark(i, j-1, id, grid, border, uf, virus);\n    }\n\n    private class Virus {\n        int id;\n        int walls;\n        Set<Integer> border;\n        Virus(int id, int walls, Set<Integer> border){\n            this.id = id;\n            this.walls = walls;\n            this.border = border;\n        }\n        Virus(){}\n    }\n\n    private class UF {\n        int[] parent;\n        int[] rank;\n        UF (int n){\n            parent = IntStream.range(0, n).toArray();\n            rank = new int[n];\n        }\n\n        private int find(int x){\n            return x == parent[x]? x : (parent[x]=find(parent[x]));\n        }\n\n        private boolean isRoot(int x){\n            return x == parent[x];\n        }\n\n        private void union(int x, int y){\n            x = find(x);\n            y = find(y);\n            if (x==y)\n                return;\n            if (rank[x]>rank[y]){\n                parent[y]=x;\n            }else{\n                parent[x]=y;\n                if (rank[x]==rank[y]){\n                    rank[y]++;\n                }\n            }\n        }\n    }\n}\n```
['Java']