Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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.

Examples

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Solution

Looks like a graph problem, with finding connected components.

Method 1 - DFS with Sinking of Island

The basic idea of the following solution is merging adjacent lands, and the merging should be done recursively. Involves array modification. We will set values to X, by doing dfs on it till the point we reach the island. Once, done, we check for next 1 which is not yet updated.

Each element is visited once only. So time is O(m*n).

public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;

	int m = grid.length;
	int n = grid[0].length;

	int count = 0;
	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (grid[i][j] == '1') {
				count++;
				merge(grid, i, j);
			}
		}
	}

	return count;
}

public void merge(char[][] grid, int i, int j) {
	int m = grid.length;
	int n = grid[0].length;

	if (i<0 || i >= m || j<0 || j >= n || grid[i][j] != '1')
		return;

	grid[i][j] = 'X';

	merge(grid, i - 1, j);
	merge(grid, i + 1, j);
	merge(grid, i, j - 1);
	merge(grid, i, j + 1);
}

Method 2 - BFS and Visited Set

Similar to above approach, but we will use set for visited nodes. Also, we will use queue instead of stack.

public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;

	int m = grid.length;
	int n = grid[0].length;
	Set<Pair<Integer, Integer>> visited = new HashSet<>();

	int count = 0;
	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (grid[i][j] == '1' && !visisted.contains(new Pair<>(i, j))) {
				count++;
				bfs(grid, i, j);
			}
		}
	}

	return count;
}

public void bfs(int r, int c, Set<Pair<Integer, Integer>> visited) {
	Queue<Pair<Integer, Integer>> q = new LinkedList<>();

	int m = grid.length;
	int n = grid[0].length;
	
	Pair<Integer, Integer> p = new Pair<>(r, c);
	
	visited.push(p);
	q.add(p)

	int[] dx = {-1, 1, 0, 0	};
	int[] dy = { 0, 0, -1, 1 };
	while (!q.isEmpty()) {
		for (int k = 0; k<4; k++) {
			int newR = r + dx[k];
			int newC = c + dy[k];
			if (newR >= 0 && newR<m && newC >= 0 && newC<n && grid[x][y] == '1' && !visited.contains(new Pair<>(newR, newC))) {
				q.add(new Pair<>(newR, newC));
				visited.add(new Pair<>(newR, newC));
			}
		}
	}
	
}

Method 3 - Union-Find

Time is O(m*n*log(k)).

public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;

	int m = grid.length;
	int n = grid[0].length;

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

	int[] root = new int[m * n];

	int count = 0;
	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (grid[i][j] == '1') {
				root[i * n + j] = i * n + j;
				count++;
			}
		}
	}

	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (grid[i][j] == '1') {
				for (int k = 0; k<4; k++) {
					int x = i + dx[k];
					int y = j + dy[k];

					if (x >= 0 && x<m && y >= 0 && y<n && grid[x][y] == '1') {
						int cRoot = getRoot(root, i * n + j);
						int nRoot = getRoot(root, x * n + y);
						if (nRoot != cRoot) {
							root[cRoot] = nRoot; //update previous node's root to be current
							count--;
						}

					}
				}
			}
		}
	}

	return count;
}

public int getRoot(int[] arr, int i) {
	while (arr[i] != i) {
		i = arr[arr[i]];
	}

	return i;
}