The Number Of Islands

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.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] is '0' or '1'.

Solutions

public class Solution {
    public int NumIslands(char[][] grid)
    {
        int count = 0;
        int N=grid.Length;
        int M=grid[0].Length;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (grid[i][j] == '1')
                {
                    count++;
                    ResetLand(grid, N, M, i, j);
                }
            }
        }

        return count;
    }
    public void ResetLand(char[][] grid, int n, int m, int i, int j)
    {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0') return;

        grid[i][j] = '0';
        ResetLand(grid, n, m, i + 1, j);
        ResetLand(grid, n, m, i - 1, j);
        ResetLand(grid, n, m, i, j + 1);
        ResetLand(grid, n, m, i, j - 1);
    }
}

Time Complexity: (N*M)

The time complexity of this algorithm is O(NM), where N is the number of rows and M is the number of columns in the grid. This is because the algorithm visits each cell in the grid once in the outer loop, and for each cell that contains a ‘1’, it calls the ResetLand method, which takes O(NM) time in the worst case (when all cells in the grid contain a ‘1’).

Space Complexity: (N*M)

The space complexity of this algorithm is O(NM) as well, due to the recursive call stack of the ResetLand method. In the worst case, when all cells in the grid contain a ‘1’, the maximum depth of the recursive call stack will be NM.