Number of Islands Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/number-of-islands

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a 2-D matrix surface of size n*m. Each cell of the surface is either 1 (land) or 0 (water).
Find the number of islands on the surface. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the surface are all surrounded by water.

Approach

This problem can be solved by using DFS on Grid algorithm. Observe that if every cell of ‘1’ adjacent to each to other can be considered to be a single component, then the problem converts to finding the number of connected components in a graph, which can be easily done using DFS / BFS.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation (DFS)

C++

bool isValid(vector<vector<int>> &surface, int i, int j) {
	return (i >= 0 && j >= 0 && j < surface[0].size() && i < surface.size() && surface[i][j] == 1);
}
void dfsOnGrid(vector<vector<int>> &surface, vector<vector<bool>> &vis, int i, int j) {
	vis[i][j] = true;
	if(isValid(surface, i + 1, j) && !vis[i + 1][j]) {
		dfsOnGrid(surface, vis, i + 1, j);
	}
	if(isValid(surface, i - 1, j) && !vis[i - 1][j]) {
		dfsOnGrid(surface, vis, i - 1, j);
	}
	if(isValid(surface, i, j + 1) && !vis[i][j + 1]) {
		dfsOnGrid(surface, vis, i, j + 1);
	}
	if(isValid(surface, i, j - 1) && !vis[i][j - 1]) {
		dfsOnGrid(surface, vis, i, j - 1);
	}
}
int getNumberOfIslands(vector<vector<int>> surface) {
    vector<vector<bool>> vis(surface.size(), vector<bool> (surface[0].size(), false));
	int connectedComponents = 0;
	for(int i = 0; i < surface.size(); i++) {
		for(int j = 0; j < surface[0].size(); j++) {
			if(!vis[i][j] && surface[i][j] == 1) {
				connectedComponents++;
				dfsOnGrid(surface, vis, i, j);
			}
		}
	}
	return connectedComponents;
}

Java

class Solution {
	boolean isValid(int[][] surface, int i, int j) {
		return (i >= 0 && j >= 0 && j < surface[0].length && i < surface.length && surface[i][j] == 1);
	}
	void dfsOnGrid(int[][] surface, boolean[][] vis, int i, int j) {
		vis[i][j] = true;
		if(isValid(surface, i + 1, j) && !vis[i + 1][j]) {
			dfsOnGrid(surface, vis, i + 1, j);
		}
		if(isValid(surface, i - 1, j) && !vis[i - 1][j]) {
			dfsOnGrid(surface, vis, i - 1, j);
		}
		if(isValid(surface, i, j + 1) && !vis[i][j + 1]) {
			dfsOnGrid(surface, vis, i, j + 1);
		}
		if(isValid(surface, i, j - 1) && !vis[i][j - 1]) {
			dfsOnGrid(surface, vis, i, j - 1);
		}
	}
	int getNumberOfIslands(int[][] surface) {
		boolean[][] vis = new boolean[surface.length][surface[0].length];
		int connectedComponents = 0;
		for(int i = 0; i < surface.length; i++) {
			for(int j = 0; j < surface[0].length; j++) {
				if(!vis[i][j] && surface[i][j] == 1) {
					connectedComponents++;
					dfsOnGrid(surface, vis, i, j);
				}
			}
		}
		return connectedComponents;
	}
}

Implementation(BFS)

C++

void bfsOnGrid(vector<vector<int>> &surface, vector<vector<bool>> &visited, int i, int j) {
	visited[i][j] = true;
	queue<pair<int, int>> queue;
	queue.push({i, j});
	while(!queue.empty()) {
		pair<int, int> point = queue.front();
		int x = point.first;
		int y = point.second;
		queue.pop();
		if(x - 1 >= 0 && surface[x - 1][y] == 1 && visited[x - 1][y] == false) {
			queue.push({x - 1, y});
			visited[x - 1][y] = true;
		}
		if(x + 1 < surface.size() && surface[x + 1][y] == 1 && visited[x + 1][y] == false) {
			queue.push({x + 1, y});
			visited[x + 1][y] = true;
		}
		if(y - 1 >= 0 && surface[x][y - 1] == 1 && visited[x][y - 1] == false) {
			queue.push({x, y - 1});
			visited[x][y - 1] = true;
		}
		if(y + 1 < surface[0].size() && surface[x][y + 1] == 1 && visited[x][y + 1] == false) {
			queue.push({x, y + 1});
			visited[x][y + 1] = true;
		}
	}
}
int getNumberOfIslands(vector<vector<int>> surface) {
    vector<vector<bool>> visited(surface.size(), vector<bool>(surface[0].size(), false));
	int connectedComponents = 0;
	for(int i = 0; i < surface.size(); i++) {
		for(int j = 0; j < surface[0].size(); j++) {
			if(!visited[i][j] && surface[i][j] == 1) {
				connectedComponents++;
				bfsOnGrid(surface, visited, i, j);
			}
		}
	}
	return connectedComponents;
}

Java

class Solution {
	class Pair {
		int first, second;
		Pair (int first, int second) {
			this.first = first;
			this.second = second;
		}
	}
	void bfsOnGrid(int[][] surface, boolean[][] visited, int i, int j) {
		visited[i][j] = true;
		Queue<Pair> queue = new LinkedList<Pair>();
		queue.add(new Pair(i, j));
		while(!queue.isEmpty()) {
			Pair point = queue.poll();
			int x = point.first;
			int y = point.second;
			if(x - 1 >= 0 && surface[x - 1][y] == 1 && visited[x - 1][y] == false) {
				queue.add(new Pair(x - 1, y));
				visited[x - 1][y] = true;
			}
			if(x + 1 < surface.length && surface[x + 1][y] == 1 && visited[x + 1][y] == false) {
				queue.add(new Pair(x + 1, y));
				visited[x + 1][y] = true;
			}
			if(y - 1 >= 0 && surface[x][y - 1] == 1 && visited[x][y - 1] == false) {
				queue.add(new Pair(x, y - 1));
				visited[x][y - 1] = true;
			}
			if(y + 1 < surface[0].length && surface[x][y + 1] == 1 && visited[x][y + 1] == false) {
				queue.add(new Pair(x, y + 1));
				visited[x][y + 1] = true;
			}
		}
	}
	int getNumberOfIslands(int[][] surface) {
    	boolean[][] visited = new boolean [surface.length][surface[0].length];
		int connectedComponents = 0;
		for(int i = 0; i < surface.length; i++) {
			for(int j = 0; j < surface[0].length; j++) {
				if(!visited[i][j] && surface[i][j] == 1) {
					connectedComponents++;
					bfsOnGrid(surface, visited, i, j);
				}
			}
		}
		return connectedComponents;
	}
}