Java DFS Solution | O(m*n) | beats 93%
\n\tpublic int largestIsland(int[][] grid) {\n\n\t\tint max_area = 1;\n\t\tint row = grid.length;\n\t\tint col = grid[0].length;\n\t\tint[] colors = new int[row
\n\tpublic int largestIsland(int[][] grid) {\n\n\t\tint max_area = 1;\n\t\tint row = grid.length;\n\t\tint col = grid[0].length;\n\t\tint[] colors = new int[row * col + 2];\n\t\tboolean[][] visited = new boolean[row][col];\n\t\tint[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };\n\t\tint index = 2;\n\n\t\tfor (int i = 0; i < row; i++) {\n\t\t\tfor (int j = 0; j < col; j++) {\n\t\t\t\tif (grid[i][j] == 1) {\n\t\t\t\t\tint area = dfsHelper(grid, visited, i, j, row, col, index, dirs);\n\t\t\t\t\tcolors[index++] = area;\n\t\t\t\t\tmax_area = Math.max(area, max_area);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\tfor (int i = 0; i < row; i++) {\n\t\t\tfor (int j = 0; j < col; j++) {\n\t\t\t\tif (grid[i][j] == 0) {\n\t\t\t\t\tint ans = 0;\n\t\t\t\t\tHashSet<Integer> set = new HashSet<Integer>();\n\t\t\t\t\tfor (int[] dir : dirs) {\n\t\t\t\t\t\tint r = i + dir[0];\n\t\t\t\t\t\tint c = j + dir[1];\n\t\t\t\t\t\tif (r < 0 || c < 0 || r >= row || c >= col || grid[r][c] == 0)\n\t\t\t\t\t\t\tcontinue;\n\t\t\t\t\t\tset.add(grid[r][c]);\n\t\t\t\t\t}\n\t\t\t\t\tfor (int node : set)\n\t\t\t\t\t\tans += colors[node];\n\t\t\t\t\tans += 1;\n\t\t\t\t\tmax_area = Math.max(ans, max_area);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\treturn max_area;\n\t}\n\n\tpublic int dfsHelper(int[][] grid, boolean[][] visited, int i, int j, int row, int col, int color, int[][] dirs) {\n\n\t\tvisited[i][j] = true;\n\t\tgrid[i][j] = color;\n\t\tint area = 1;\n\t\tfor (int[] dir : dirs) {\n\t\t\tint r = i + dir[0];\n\t\t\tint c = j + dir[1];\n\t\t\tif (r < 0 || c < 0 || r >= row || c >= col || grid[r][c] == 0 || visited[r][c])\n\t\t\t\tcontinue;\n\t\t\tarea += dfsHelper(grid, visited, r, c, row, col, color, dirs);\n\t\t}\n\t\treturn area;\n\t}\n
[]