Number of Islands

Given a 2D grid consisting of either '1' or '0' character at each position. '1' represents land and '0' represents water. An island is a mass of land which is surrounded by water. Count the number of islands.

.

Example Test Cases

Sample Test Case 1

Input grid:
11110
11010
11000
00000
Expected Output: 1
Explanation: There is only one island starting at position (0, 0) , since this island will be composed of every land available in the grid.

Sample Test Case 2

Input grid:
11000
11000
00100
00011
Expected Output: 3
Explanation: There are three islands: starting at position (0, 0) , (2, 2) and (3, 3) respectively.

Solution

If we imagine this 2d grid in the form of a graph, then it means that the answer to this problem is the number of connected components within the graph. We can easily find the number of connected components by applying DFS through the grid as shown below

Implementation

#include <iostream>
#include <vector>
using namespace std;

// This method starts the DFS process from position (x, y).
void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<bool>>& visited) {
    // Only visit the position (x, y) if it has not been visited before.
    if (visited[x][y] == false) {
        visited[x][y] = true;
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
            	// Since, we only want to traverse in horizontal and vertical direction.
                if (abs(i) + abs(j) != 1) continue;
                
                // To make sure that we don't go out of the grid.
                if (x + i < 0 || x + i >= grid.size() || y + j < 0 || y + j >= grid[x].size()) continue;
                
                // Don't visit a position which has water.
                if (grid[x + i][y + j] == '0') continue;
                
                dfs(x + i, y + j, grid, visited);
            }
        }
    }    
}

int main() {
	vector<vector<char>> grid = { {'1', '1', '1', '0' }, { '0', '0', '0', '1' } }; 
    int n = grid.size();
    vector<vector<bool>> visited(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < grid[i].size(); j++) {
            visited[i].push_back(false);
        }
    }
    
    int noOfIslands = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < grid[i].size(); j++) {
            if (visited[i][j] == false && grid[i][j] == '1') {
                dfs(i, j, grid, visited);
                noOfIslands++;
            }
        }
    }
    
    cout << "No of islands are " << noOfIslands << "\n";
}
view raw
noOfIslands.cpp hosted with ❤ by GitHub