[C++/Java/Python] Straight Forward O(N^2) with Explanations
PreWord\nThe solution is long, but in fact it is really straight forward.\nI suggest not going into my codes but reading my explanations, which should be enough
# PreWord\nThe solution is long, but in fact it is really straight forward.\nI suggest **not** going into my codes but reading my explanations, which should be enough.\n\n# Prepare\nI have several simple sub function to help me on this kind of problem.\n1. valid(int x, int y), check if (x, y) is valid in the grid.\n1. move(int x, int y), return all possible next position in 4 directions.\n<br>\n\n# Explanation\nOnly 2 steps:\n1. Explore every island using DFS, count its area, give it an island index and save the result to a {index: area} map.\n2. Loop every cell == 0, check its connected islands and calculate total islands area.\n<br>\n\n# Complexity\nTime `O(N^2)`\nSpace `O(N^2)`\n<br>\n\n**C++:**\n```cpp\n    int N;\n    int largestIsland(vector<vector<int>>& grid) {\n        N = grid.size();\n        //DFS every island and give it an index of island\n        int index = 2, res = 0;\n        unordered_map <int, int>area;\n        for (int x = 0; x < N; ++x) {\n            for (int y = 0; y < N; ++y) {\n                if (grid[x][y] == 1) {\n                    area[index] = dfs(grid, x, y, index);\n                    res = max(res, area[index++]);\n                }\n            }\n        }\n        //traverse every 0 cell and count biggest island it can conntect\n        for (int x = 0; x < N; ++x)\n            for (int y = 0; y < N; ++y)\n                if (grid[x][y] == 0) {\n                    unordered_set<int> seen = {};\n                    int cur = 1;\n                    for (auto p : move(x, y)) {\n                        index = grid[p.first][p.second];\n                        if (index > 1 && seen.count(index) == 0) {\n                            seen.insert(index);\n                            cur += area[index];\n                        }\n                    }\n                    res = max(res, cur);\n                }\n        return res;\n    }\n\n    vector<pair<int, int>> move(int x, int y) {\n        vector<pair<int, int>> res;\n        for (auto p : vector<vector<int>> {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}) {\n            if (valid(x + p[0], y + p[1]))\n                res.push_back(make_pair(x + p[0], y + p[1]));\n        }\n        return res;\n    }\n\n    int valid(int x, int y) {\n        return 0 <= x && x < N && 0 <= y && y < N;\n    }\n\n    int dfs(vector<vector<int>>& grid, int x, int y, int index) {\n        int area = 0;\n        grid[x][y] = index;\n        for (auto p : move(x, y))\n            if (grid[p.first][p.second] == 1)\n                area += dfs(grid, p.first, p.second, index);\n        return area + 1;\n    }\n```\n\n**Java:**\n```java\nimport javafx.util.Pair;\nclass Solution {\n    public int N = 0;\n    public int largestIsland(int[][] grid) {\n        N = grid.length;\n        //DFS every island and give it an index of island\n        int index = 3, res = 0;\n        HashMap<Integer, Integer> area = new HashMap<>();\n        for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y)\n            if (grid[x][y] == 1) {\n                area.put(index, dfs(grid, x, y, index));\n                res = Math.max(res, area.get(index++));\n            }\n\n        //traverse every 0 cell and count biggest island it can conntect\n        for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y)\n            if (grid[x][y] == 0) {\n                HashSet<Integer> seen = new HashSet<>();\n                int cur = 1;\n                for (Pair<Integer, Integer> p : move(x, y)) {\n                    index = grid[p.getKey()][p.getValue()];\n                    if (index > 1 && !seen.contains(index)) {\n                        seen.add(index);\n                        cur += area.get(index);\n                    }\n                }\n                res = Math.max(res, cur);\n            }\n        return res;\n    }\n\n    public List <Pair<Integer, Integer>> move(int x, int y) {\n        ArrayList <Pair<Integer, Integer>> res = new ArrayList<>();\n        if (valid(x, y + 1)) res.add(new Pair<Integer, Integer>(x, y + 1));\n        if (valid(x, y - 1)) res.add(new Pair<Integer, Integer>(x, y - 1));\n        if (valid(x + 1, y)) res.add(new Pair<Integer, Integer>(x + 1, y));\n        if (valid(x - 1, y)) res.add(new Pair<Integer, Integer>(x - 1, y));\n        return res;\n    }\n\n    public boolean valid(int x, int y) {\n        return 0 <= x && x < N && 0 <= y && y < N;\n    }\n\n    public int dfs(int[][] grid, int x, int y, int index) {\n        int area = 0;\n        grid[x][y] = index;\n        for (Pair<Integer, Integer> p : move(x, y))\n            if (grid[p.getKey()][p.getValue()] == 1)\n                area += dfs(grid, p.getKey(), p.getValue(), index);\n        return area + 1;\n    }\n}\n\n\n```\n**Python:**\n```py\n    def largestIsland(self, grid):\n        N = len(grid)\n\n        def move(x, y):\n            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n                if 0 <= x + i < N and 0 <= y + j < N:\n                    yield x + i, y + j\n\n        def dfs(x, y, index):\n            res = 0\n            grid[x][y] = index\n            for i, j in move(x, y):\n                if grid[i][j] == 1:\n                    res += dfs(i, j, index)\n            return res + 1\n\n        # DFS every island and give it an index of island\n        index = 2\n        areas = {0: 0}\n        for x in xrange(N):\n            for y in xrange(N):\n                if grid[x][y] == 1:\n                    areas[index] = dfs(x, y, index)\n                    index += 1\n\n        # traverse every 0 cell and count biggest island it can conntect\n        res = max(areas.values())\n        for x in xrange(N):\n            for y in xrange(N):\n                if grid[x][y] == 0:\n                    possible = set(grid[i][j] for i, j in move(x, y))\n                    res = max(res, sum(areas[index] for index in possible) + 1)\n        return res\n```\n
[]