Number of Islands

(Grid Version)

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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.

Practice Link

Sample#

OUTPUT: 4

DFS#

The grid is treated as a graph where each '1' cell is a node connected to its four horizontal/vertical neighbors. Every time we discover an unvisited '1' cell, it must belong to a new island — we then flood-fill the entire connected component (marking cells '*' to avoid revisiting) via DFS before incrementing the island count. The total number of DFS initiations equals the number of islands.

• Iterate over every cell; when a '1' is found, increment the island counter and launch DFS from that cell.
• DFS marks the current land cell as visited (overwrite with '*') and recurses in all four directions.
• A cell is skipped if it is out-of-bounds, is water ('0'), or is already visited ('*').
• Because we mark cells in-place, no separate visited array is needed — the modification of the grid itself serves as the visited record.

Implementation#

class Solution {
public:
    vector<int> dx={1,-1,0,0};
    vector<int> dy={0,0,1,-1};

    bool isValidCell(vector<vector<char>>& grid, int i, int j)
    {
        if(i<0 || i>= grid.size() || j<0 ||j>=grid[0].size() || grid[i][j]!='1')
            return false;
        return true;
    }
    void visitIslands(vector<vector<char>>& grid,int i, int j)
    {

        for(int dir=0;dir<4;dir++)
        {
            int ni = i + dx[dir];
            int nj = j + dy[dir];

            if(isValidCell(grid, ni,nj)){
                grid[ni][nj] = '*';
                visitIslands(grid, ni,nj);
            }
                
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int islands = 0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1')
                {
                    visitIslands(grid, i, j);
                    islands++;

                }
            }
        }
        return islands;
    }
};

Complexities#

Time Complexity - O(V^2)

Space Complexity - Auxilary Space