LeetCode : 827. Making A Large Island

[congr]

https://leetcode.com/problems/making-a-large-island/

[congr]

class Solution {
    public int largestIsland(int[][] grid) {
        Map<Integer, Integer> map = new HashMap();
        int N = grid.length;
        int mark = 2;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    int cnt = dfs(grid, i, j, mark);
                    map.put (mark, cnt);
                    mark++;
                }
            }
        }

        // chage 0 to 1
        int max = map.getOrDefault(2, 0); // !!!!!
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 0) {
                    int sum = 1;
                    Set<Integer> set = new HashSet();
                    for (int d = 0; d < 4; d++) {
                        int ny = i + dy[d], nx = j + dx[d];
                        if (!inside(ny, nx, N) || set.contains(grid[ny][nx])) continue;
                        set.add(grid[ny][nx]);
                        sum += map.getOrDefault(grid[ny][nx], 0);
                    }
                    max = Math.max(max, sum);  // add the 0 cell itself
                }
            }
        }

        return max;
    }

    int dfs(int[][] grid, int y, int x, int mark) {
        grid[y][x] = mark;

        int cnt = 1; // start at 1, the current grid cell
        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d], nx = x + dx[d];
            if (inside(ny, nx, grid.length) && grid[ny][nx] == 1) 
                cnt += dfs(grid, ny, nx, mark);
        }    

        return cnt;
    }

    int[] dx = {0,-1,0,1};
    int[] dy = {-1,0,1,0};

    boolean inside(int y, int x, int N) {
        if (y >= 0 && x >= 0  && y < N && x < N) return true;
        return false;
    }
}

[congr]

https://leetcode.com/problems/making-a-large-island/discuss/127015/C%2B%2B-O(n*m)-15-ms-colorful-islands