AC Java Solution using Union-Find with explanations


  • 9
    B

    It is a classical DFS problem, and my solution applied union-find algorithm that passed all the test cases.
    Basic idea is to iterate through every node's neighbours and marked them if they aren't connected.
    Finally, if it was the root node then increase the total number of islands.

    public class Solution {

    private int[] sz;
    private int[] id;
    private int N, M;
    
    public int find(int p) {
    	while (id[p] != p) 
    		p = id[p];
    	return p;
    }
    
    public void union(int p, int q) {
    	int rootP = find(p);
    	int rootQ = find(q);
    	if (rootP == rootQ) return;
    	
    	if (sz[rootP] < sz[rootQ])	{sz[rootQ] += sz[rootP]; id[rootP] = id[rootQ];}
    	else 						{sz[rootP] += sz[rootQ]; id[rootQ] = id[rootP];}
    }
    
    private boolean inside(int x, int y) {
    	return (x >= 0 && y >= 0 && x < N && y < M);
    }
    
    public int numIslands(char[][] grid) {
    	if (grid == null || grid.length ==0) return 0;
    	N = grid.length;
    	M = grid[0].length;
    	sz = new int[N*M];
    	id = new int[N*M];
    	for (int i = 0; i < N*M; i++) {
    		id[i] = i;
    		sz[i] = 1;
    	}
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) 
        		if (grid[i][j] != '0') {
            		int tmp = i*M + j;
            		if (inside(i-1, j) && grid[i-1][j] != '0') union(tmp, tmp - M);
            		if (inside(i, j-1) && grid[i][j-1] != '0') union(tmp, tmp - 1);
            		if (inside(i+1, j) && grid[i+1][j] != '0') union(tmp, tmp + M);
            		if (inside(i, j+1) && grid[i][j+1] != '0') union(tmp, tmp + 1);
            	}
        }
        int islands = 0, i = 0;
        while (i < N*M) {
        	if (i == id[i] && grid[i/M][i%M] != '0') islands++;
        	i++;
        }
        return islands;
    }
    

    }


  • 0
    A

    It looks like the sz array is never initialized and so contains 0 for the whole run. So every call to union(p, q) ends up setting the representative of q to be the representative of p. I guess this is never an issue the way you call it with the visited node as the first parameter.

    Thanks for teaching me about union-find.


  • 0
    B

    Thanks for your comments. I have initialised sz array with 1 now and it works.


  • 0
    O

    It will be much faster if you compress the union find path.


Log in to reply
 

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