Number of Islands

LeetCode Q 200 - Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
Input:
11110
11010
11000
00000
Output: 1

Example 2:
Input:
11000
11000
00100
00011
Output: 3

Solution

Solution 1 : DFS

We don’t need another boolean[][] visited, since we can set the visited element grid[r][c] = '0' to avoid re-visit.
Time complexity : R C nodes, O(R C)

Code:

private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
public int numIslands (char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
	
	int count = 0;
	for (int i = 0; i < grid.length; i++) {
		for (int j = 0; j < grid[i].length; j++) {
			if (grid[i][j] == '1') {
				dfs(grid, i, j);
				count++;
			}
		}
	}

	return count;
}

private void dfs (char[][] grid, int r, int c) {
	if (r < 0 || c < 0 || r == grid.length || c == grid[0].length || grid[r][c] != '1')
		return;

	grid[r][c] = '0';
	for (int i = 0; i < 4; i++) 
		dfs(grid, r + DIRS[i], c + DIRS[i + 1]);

	return;
}

Solution 2 : BFS

Code:

private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
public int numIslands (char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
	
	int R = grid.length, C= grid[0].length;

	int count = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == '1') {
				Queue<int[]> que = new LinkedList<>();
				que.offer(new int[]{r, c});
				
				while (!que.isEmpty()) {
					int[] curr = que.poll();
					grid[curr[0]][curr[1]] = '0';
					for (int i = 0; i < 4; i++) {
						int nr = curr[0] + DIRS[i];
						int nc = curr[1] + DIRS[i + 1];
						if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] == '1') 
							que.offer(new int[]{nr, nc});
					}
				}

				count++;
			}
		}
	}

	return count;
}

Solution 3 : Disjoint Set

Code:

class UnionFindSet {
	int[] parent;
	int count;

	public UnionFindSet (int size) {
		this.parent = new int[size];
		for (int i = 0; i < size; i++) 
			this.parent[i] = i;
	}

	public int find (int x) {
		if (parent[x] != x) 
			parent[x] = find(parent[x]);
		return parent[x];
	}

	public void union (int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) {
			parent[px] = py;
			count--;
		}
	}
}
private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

	int R = grid.length, C= grid[0].length;   
	
	UnionFindSet ufs = new UnionFindSet(R * C);

	int total = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == '1') total++;
		}
	}

	ufs.count = total;

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == '1') {
				for (int i = 0; i < 4; i++) {
					int nr = r + DIRS[i], nc = c + DIRS[i + 1];
					if (nr < 0 || nc < 0 || nr == R || nc == C || grid[nr][nc] != '1') continue;
					ufs.union(r * C + c, nr * C + nc);
			    }
			}
		}
	}

	return ufs.count;
}