Graph: Find the number of Islands

Problem Statement:

You are given a n * m matrix, where ‘w’ is water and ‘l’ is land.

You need to count the number of islands.

An island is a group of adjacent ‘l’, where in the cells are connected horizontally or vertically and is surrounded by water.

Example:

Input:

Output:
3

Solution 1: DFS

Each time we find 1, that is a new island, and increment the island count.

Then call dsf_solution_helper, that will erase the islands that are connected to the current island by making it to 0.

We perform this, so as to prevent the repeated counts.

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

Solution 2: BFS

In DSF we used recursion, if we do not need recursion, we will use BFS.

In BFS we will use queue to solve the problem.

Once we find an island, use BFS to explore all connected cells and mark them as visited.

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

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void dsf_solution_helper(vector<vector<char>>& grid, int i, int j) 
{
    int m = grid.size(), n = grid[0].size();

    if (i < 0 || i == m || j < 0 || j == n || grid[i][j] == '0') 
    {
        return; // out of bounds or water
    }

    grid[i][j] = '0'; // mark as visited by making connected island as visited
    dsf_solution_helper(grid, i - 1, j); // up
    dsf_solution_helper(grid, i + 1, j); // down
    dsf_solution_helper(grid, i, j - 1); // left
    dsf_solution_helper(grid, i, j + 1); // right
}

int dsf_solution (vector<vector<char>>& grid) {
    int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                islands++;                  // found a new island
                dsf_solution_helper(grid, i, j);   // sink it (DFS)
            }
        }
    }
    return islands;
}


int bsf_solution(vector<vector<char>>& grid) 
{
    if (grid.empty() || grid[0].empty()) 
    {
        return 0;
    }
    
    int islands = 0;
    int m = grid.size();
    int n = grid[0].size();
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    queue<pair<int, int>> q;
    
    for (int i = 0; i < m; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            if (grid[i][j] == '1') 
            {
                islands++;
                q.push({i, j});
                
                while (!q.empty()) 
                {
                    auto [x, y] = q.front();
                    q.pop();
                    
                    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != '1') 
                    {
                        continue;
                    }
                    
                    grid[x][y] = '0'; // mark as visited
                    
                    for (auto& dir : directions) 
                    {
                        int nx = x + dir.first;
                        int ny = y + dir.second;
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') 
                        {
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    
    return islands;
}

int main() 
{
    vector<vector<char>> grid = 
    {
        {'1', '1', '0', '0', '0'},
        {'0', '1', '0', '0', '1'},
        {'1', '0', '0', '1', '1'},
        {'0', '0', '0', '0', '0'},
        {'1', '0', '1', '1', '0'}
    };

    cout << dsf_solution(grid) << endl;

    grid = 
    {
        {'1', '1', '0', '0', '0'},
        {'0', '1', '0', '0', '1'},
        {'1', '0', '0', '1', '1'},
        {'0', '0', '0', '0', '0'},
        {'1', '0', '1', '1', '0'}
    };    
    cout << bsf_solution(grid) << endl;
    return 0;
}

Output

5
5