C++: Number of Islands

Thought Process

The problem requires counting the number of islands in a 2D grid. An island is represented by '1's (land) and is surrounded by '0's (water). The key idea is to traverse the grid and use Depth-First Search (DFS) to explore all connected land cells starting from an unvisited '1'. Each DFS call marks all reachable land cells as visited, ensuring they are not counted again. Further, we use a visited matrix to keep track of visited cells. For each unvisited '1', we increment the island count and perform DFS to mark all connected land cells. 

class Solution {
public:
    int vis[301][301];
    void dfs(vector<vector<char>>& grid, int sr, int sc){

        if(sr>=grid.size() || sc>=grid[0].size() || sr<0 || sc<0 || vis[sr][sc]==1 || grid[sr][sc]=='0')
            return;

        // Traverse in all four directions
        vis[sr][sc]=1;
        dfs(grid,sr+1,sc);
        dfs(grid,sr-1,sc);
        dfs(grid,sr,sc+1);
        dfs(grid,sr,sc-1);   
    }

    // Basically, we are counting number of connected components
    int numIslands(vector<vector<char>>& grid) {

        int row = grid.size();
        int col = grid[0].size();
        memset(vis,0,sizeof(vis));

        int noOfIslands=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                
                // If it is land and it is not visited then visit it.
                if(vis[i][j]==0 && grid[i][j]=='1'){
                    dfs(grid,i,j);
                    noOfIslands++;
                } 
            }
        }
        return noOfIslands;
    }
};

Code Complexity

Time Complexity: O(n * m)

The algorithm visits each cell in the grid once, where 'n' is the number of rows and 'm' is the number of columns.

Space Complexity: O(n * m)

The algorithm uses a visited matrix of size n * m to keep track of visited cells, where 'n' is the number of rows and 'm' is the number of columns.

Code copied!