Problem Statement

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.

Solution Explanation

Given that in a 2D grid, all the 1's are lands and adjacent(horizantal and vertical) things also add up to the island, we need a way to mark all adjacent lands.
For example the below grid consist of only one island since all the lands are adjacent to each other.

11110
11010
11000
00000

The core logic of solving this problem lies in using Depth First Search(DFS), which involves marking the neighbors as visited once you visit a unvisited land.

We can keep a 2D boolean array called 'visited' and everytime you visit a land which is not visited, you increment the count of islands and mark all of its neighbors as visited. Finally return the island count.

Below is the java implementation of number of islands,

public class NumberOfIslands {

	private int h;
	private int w;

	public static void main(String[] args) {
		char[][] grid = { { '1', '1', '1' }, { '1', '0', '0' }, { '1', '0', '1' } };
		System.out.println("Number of islands is " + new NumberOfIslands().numIslands(grid));
	}

	public int numIslands(char[][] grid) {
		h = grid.length;
		if (h == 0)
			return 0;
		w = grid[0].length;
		boolean[][] visited = new boolean[h][w];
		int islandCount = 0;
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				if (!visited[i][j] && grid[i][j] == '1') {
					markNeigbors(grid, visited, i, j);
					++islandCount;
				}
			}
		}
		return islandCount;
	}

	private void markNeigbors(char[][] grid, boolean[][] visited, int x, int y) {
		if (x < 0 || x >= h || y < 0 || y >= w || visited[x][y] || grid[x][y] != '1')
			return;
		visited[x][y] = true;
		markNeigbors(grid, visited, x + 1, y);
		markNeigbors(grid, visited, x - 1, y);
		markNeigbors(grid, visited, x, y + 1);
		markNeigbors(grid, visited, x, y - 1);

	}

}

Time Complexity

The time complexity is O(n^2) since we do one pass of the whole grid.