JAVA UnionFind O(mn) time complexity (22ms)
You can simply use this as a template for most "large islands" problems.\nFirst go over all grid and connect all single "islands", while counting their area. Th
You can simply use this as a template for most "large islands" problems.\nFirst go over all grid and connect all single "islands", while counting their area. This is typical move for all island problem using UnionFind.\nThen try inserting a "1" at every existing "0" postion on the grid. This time instead of "connecting" islands together, we only add all four neighbor "islands" area.\n\nSince we use compressed find here, the average runtime is O(mn).\n\n```\nclass Solution {\n    public int largestIsland(int[][] grid) {\n        if (grid.length == 0 || grid[0].length == 0) return 0;\n        int row = grid.length, col = grid[0].length;\n        int[] father = new int[row * col];\n        int[] area = new int[row * col];\n        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        \n        for (int i = 0; i < father.length; ++i) father[i] = i;\n        \n        int max = 0;\n        for (int i = 0; i < row; ++i) {\n            for (int j = 0; j < col; ++j) {\n                if (grid[i][j] == 0) continue;\n                int fy = i * col + j;\n                area[fy] = 1;\n                if (i > 0 && grid[i - 1][j] == 1) {\n                    //int fx = find(father, i * col + j);\n                    fy = find(father, i * col + j - col);\n                    father[i * col + j] = fy;\n                    area[fy]++;\n                }\n                if (j > 0 && grid[i][j - 1] == 1) {\n                    int fx = find(father, i * col + j);\n                    fy = find(father, i * col + j - 1);\n                    if (fx != fy) {\n                        father[fx] = fy;\n                        area[fy] += area[fx];\n                    }\n                }\n                max = Math.max(max, area[fy]);\n            }\n        }\n        \n        for (int i = 0; i < row; ++i) {\n            for (int j = 0; j < col; ++j) {\n                if (grid[i][j] == 1) continue;\n                int f0 = i * col + j;\n                area[f0] = 1;\n                Set<Integer> nb = new HashSet();\n                for (int k = 0; k < 4; ++k) {\n                    int x = i + d[k][0], y = j + d[k][1];\n                    if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == 0)\n                        continue;\n                    int f1 = find(father, x * col + y);\n                    if (!nb.contains(f1)) {\n                        nb.add(f1);\n                        area[f0] += area[f1];\n                    }\n                }\n                max = Math.max(area[f0], max);\n            }\n        }\n        return max;\n    }\n    \n    private int find(int[] father, int x) {\n        int parent = father[x];\n        while (parent != father[parent]) {\n            parent = father[parent];\n        }\n        int temp = -1;\n        int fx = x;\n        while (fx != parent) {\n            temp = father[fx];\n            father[fx] = parent;\n            fx = temp;\n        }\n        return parent;\n    }\n}\n```
[]