Java Plain dfs to merge, 28 ms


  • 0
    V

    This is using dfs, idea is to have a counter incremented for every disconnected group, and during merge decrease the counter and bring the "to be merged" group into the same group by running dfs on it to change its values.

        int[][] mat;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int cnt = 0, ind = 0, min = Integer.MAX_VALUE, mm, nn;
        public List<Integer> numIslands2(int m, int n, int[][] pos) 
        {
            int cnt = 0, ind = 0;
            mm = m; nn = n;
            List<Integer> toRet = new ArrayList<Integer>();
            int x, y;
            mat = new int[m][n];
            for(int i = 0; i < pos.length; i++)
            {
                min = Integer.MAX_VALUE;
                for(int j = 0; j < dirs.length; j++)
                {
                    x = dirs[j][0] + pos[i][0];
                    y = dirs[j][1] + pos[i][1];
                    if(x < 0 || y < 0 || x >= m || y >= n || mat[x][y] == 0)
                        continue;
                    min = Math.min(min, mat[x][y]);
                }
                if(min == Integer.MAX_VALUE)
                {
                    cnt ++; ind++;
                    mat[pos[i][0]][pos[i][1]] = ind;
                    toRet.add(cnt);
                    continue;
                }
                mat[pos[i][0]][pos[i][1]] = min;
                for(int j = 0; j < dirs.length; j++)
                {
                    x = dirs[j][0] + pos[i][0];
                    y = dirs[j][1] + pos[i][1];
                    if(x < 0 || y < 0 || x >= m || y >= n || mat[x][y] == 0 || mat[x][y] == min)
                        continue;
                    dfs(x, y, min, mat[x][y]);
                    cnt--;
                }   
                toRet.add(cnt);
            }
            return toRet;
        }
        void dfs(int i, int j, int toVal, int currVal)
        {
            mat[i][j] = toVal;
            int x , y;
            for(int k = 0; k < dirs.length; k++)
            {
                x = dirs[k][0] + i;
                y = dirs[k][1] + j;
                if(x < 0 || y < 0 || x >= mm || y >= nn || mat[x][y] != currVal)
                    continue;
                dfs(x, y, toVal, currVal);
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.