827. Making A Large Island

// Time: O(n2), Space: O(n2)
// https://leetcode.com/problems/making-a-large-island/discuss/127015/C%2B%2B-O(n*m)-15-ms-colorful-islands
class Solution {
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int c = 2;
        int n = grid.length;
        int m = grid[0].length;
        HashMap<Integer, Integer> islandCount = new HashMap<>();
        int[][] dirs = { {0,1}, {0,-1}, {1,0}, {-1,0} };

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, n, m, c, islandCount, dirs);
                    c++;
                }
            }
        }

        int res = 0;
        for (int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if (grid[i][j] == 0) {
                    HashSet<Integer> seen = new HashSet<>();
                    int tmp = 1;

                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];

                        if (x<0 || x>=n || y<0 || y>=m || grid[x][y] == 0 || seen.contains(grid[x][y])) {
                            continue;
                        }

                        tmp += islandCount.get(grid[x][y]);
                        seen.add(grid[x][y]);
                    }

                    res = Math.max(res, tmp);
                } else {
                    res = Math.max(res, islandCount.get(grid[i][j]));
                }
            }
        }

        return res;
    }

    public void dfs(int[][] grid, int i, int j, int n, int m, int c, HashMap<Integer, Integer> islandCount, int[][] dirs) {
        if (i<0 || i>=n || j<0 || j>=m || grid[i][j] != 1) {
            return;
        }

        grid[i][j] = c;
        islandCount.put(c, islandCount.getOrDefault(c,0)+1);

        for (int[] dir : dirs) {
            dfs(grid, i + dir[0], j + dir[1], n, m, c, islandCount, dirs);
        }
    }
}