Find The Number Of Islands

Given a grid of size n*m (n is the number of rows and m is the number of columns in the grid) consisting of ‘0’s (Water) and ‘1’s(Land). Find the number of islands.

Note: An island is either surrounded by water or the boundary of a grid and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions.

Examples:

Input: grid = [[0,1],[1,0],[1,1],[1,0]]
Output: 1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.

Input: grid = [[0,1,1,1,0,0,0],[0,0,1,1,0,1,0]]
Output: 2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 2 0 
There are two islands in the grid. One island is marked by '1' and the other by '2'.

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

Constraints:
1 ≤ n, m ≤ 500
0 ≤ grid[i][j] ≤ 1Given a grid of size n*m (n is the number of rows and m is the number of columns in the grid) consisting of ‘0’s (Water) and ‘1’s(Land). Find the number of islands.

Note: An island is either surrounded by water or the boundary of a grid and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions.

Examples:

Input: grid = [[0,1],[1,0],[1,1],[1,0]]
Output: 1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.

Input: grid = [[0,1,1,1,0,0,0],[0,0,1,1,0,1,0]]
Output: 2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 2 0 
There are two islands in the grid. One island is marked by '1' and the other by '2'.

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

Constraints:
1 ≤ n, m ≤ 500
grid[i][j] = {‘0’, ‘1’}

Approach 01:

class Solution {
public:
    void exploreIsland(vector<vector<char>>& grid, int row, int col) {
        int numRows = grid.size();
        int numCols = grid[0].size();
        
        // Base cases to check boundaries and if the cell is water
        if (row < 0 || row >= numRows || col < 0 || col >= numCols || grid[row][col] == '0') {
            return;
        }

        // Mark the cell as visited
        grid[row][col] = '0';

        // Explore all 8 directions
        exploreIsland(grid, row, col - 1);  // Left
        exploreIsland(grid, row, col + 1);  // Right
        exploreIsland(grid, row - 1, col);  // Up
        exploreIsland(grid, row + 1, col);  // Down
        exploreIsland(grid, row + 1, col - 1);  // Left Down Diagonal
        exploreIsland(grid, row + 1, col + 1);  // Right Down Diagonal
        exploreIsland(grid, row - 1, col - 1);  // Left Up Diagonal
        exploreIsland(grid, row - 1, col + 1);  // Right Up Diagonal
    }

    int numIslands(vector<vector<char>>& grid) {
        int numRows = grid.size();
        if (numRows == 0) return 0; // Handle empty grid case
        int numCols = grid[0].size();
        int islandCount = 0;

        for (int row = 0; row < numRows; ++row) {
            for (int col = 0; col < numCols; ++col) {
                if (grid[row][col] == '1') {
                    islandCount++;
                    exploreIsland(grid, row, col);
                }
            }
        }

        return islandCount;
    }
};

class Solution:
    def exploreIsland(self, grid, row, col):
        numRows, numCols = len(grid), len(grid[0])
        if row >= numRows or col >= numCols:
            return
        if row < 0 or col < 0:
            return
        if grid[row][col] == 0:
            return
        grid[row][col] = 0
        
        self.exploreIsland(grid, row, col - 1)  # Left
        self.exploreIsland(grid, row, col + 1)  # Right
        self.exploreIsland(grid, row - 1, col)  # Up
        self.exploreIsland(grid, row + 1, col)  # Down
        self.exploreIsland(grid, row + 1, col - 1)  # Left Down Diagonal
        self.exploreIsland(grid, row + 1, col + 1)  # Right Down Diagonal
        self.exploreIsland(grid, row - 1, col - 1)  # Left Up Diagonal
        self.exploreIsland(grid, row - 1, col + 1)  # Right Up Diagonal

    def numIslands(self, grid):
        numRows, numCols = len(grid), len(grid[0])
        islandCount = 0
        for row in range(numRows):
            for col in range(numCols):
                if grid[row][col] == 1:
                    islandCount += 1
                    self.exploreIsland(grid, row, col)

        return islandCount

Time Complexity

• Iterating through the grid:

  The function iterates through each cell in the grid, which has a total of \(n \times m\) cells, where \(n\) is the number of rows and \(m\) is the number of columns. This takes \(O(n \times m)\) time.

• Exploring each island:

  When the function encounters a land cell (‘1’), it invokes exploreIsland, which explores all connected land cells (the entire island). In the worst case, the exploration function may traverse all cells in the grid, leading to an additional \(O(n \times m)\) in the worst-case scenario where the entire grid is land.

• Overall Time Complexity:

  The overall time complexity is \(O(n \times m)\), where each cell is visited at most once.

Space Complexity

• Auxiliary Space:

  The space used by the recursion stack in the exploreIsland function can go as deep as \(O(n \times m)\) in the worst case (if the grid is filled with land cells). However, since the grid cells are marked as visited (turned to ‘0’), the maximum space utilized by the recursion stack is effectively limited to the size of the grid.

• Overall Space Complexity:

  The overall space complexity is \(O(n \times m)\) in the worst case due to the recursion stack. In practice, it can be more accurately described as \(O(\text{min}(n, m))\) for the depth of recursion in a balanced grid structure.