Number of Islands

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Number of Islands
Approach: Using BFS

Logicmojo - Updated Aug 28, 2021

Problem Statement: Number of Islands

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.

Example: surface: [[1, 1, 0, 1],[1, 0, 1, 1],[0, 1, 0, 1]]

Output: 3

Approach: BFS

Overall the idea is to find number of connected components.If adjacent cell is having 1, consider it as a connected node

Perform BFS and DFS at the index to make all the neighboring elements from '1' --> '0' as they are part of same island. If the interviewer says we can not mutate the array then maintain a separate m * n visited array and mark all the BFS and DFS elements as visited.

For BFS maintain a queue and push index of encountered '1' in queue and subsequently keep adding all the neighbors with value '1' till queue becomes empty.

You can either take a visited matrix or modify the same matrix making 1 as 0 ( We have modified the same matrix)

Return the count.

C++ Implementation:

class Solution {
public:
    int DR[4]={1, 0, -1, 0};
    int DC[4]={0, -1, 0, 1};
    
    bool valid_index(int i, int j, vector<vector<char>>& grid) {
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size())
            return false;
        return true;
    }
    
    void bfs(int i, int j, vector<vector<char>>& grid) {
        grid[i][j]='0';
        queue<pair<int, int>> q;
        q.push({i, j});
        while(!q.empty()) {
            int i=q.front().first;
            int j=q.front().second;
            q.pop();
            for(int k=0; k<4; k++) {
                int ci=DR[k]+i;
                int cj=DC[k]+j;
                if(!valid_index(ci, cj, grid))
                    continue;
                if(grid[ci][cj]=='1') {
                    q.push({ci, cj});
                    grid[ci][cj]='0';
                }
            }
        }
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        int no_of_islands=0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(grid[i][j]=='1') {
                    no_of_islands++;
                    bfs(i, j, grid);
                }
            }
        }
        return no_of_islands;
    }
};

Python Implementation:

from collections import deque
class Solution:
    def numIslands(self, grid):
        if not grid: return 0
        m, n = len(grid), len(grid[0])
        ans = 0
        queue = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append([i, j])
                    grid[i][j] = 2
                    while queue:
                        X = [-1, 0, 0, 1]
                        Y = [0, 1, -1, 0]
                        x, y = queue.popleft()
                        for k in range(4):
                            xx, yy = x + X[k], y + Y[k]
                            if 0 <= xx < m and 0 <= yy < n and grid[xx][yy] == 1:
                                queue.append((xx, yy))
                                grid[xx][yy] = 2
                    ans += 1            
        return ans
ob1 = Solution()
print(ob1.numIslands([[1, 1, 0, 1],[1, 0, 1, 1],[0, 1, 0, 1]]))

Time Complexity: O(m*n) in both BFS and DFS

Space Complexity: O(m*n) O(mn) in BFS as we are maintianing a queue which in worst cases can have all the elements of matrix

💡 Follow up: Try to solve it by using Union find method

With this article at Logicmojo, you must have the complete idea of solving Number of Islands problem.