Number of Islands medium

Problem Statement

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

Steps

1. Initialization: Initialize a variable numIslands to 0, which will store the count of islands.
2. Iteration: Iterate through each cell of the grid.
3. Island Detection: If a cell contains '1' (land) and hasn't been visited yet:
   • Increment numIslands.
   • Perform Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all connected land cells and mark them as visited.
4. DFS/BFS: The DFS/BFS function explores the connected land cells recursively/iteratively, marking them as visited ('0') to prevent revisits.
5. Return: After iterating through the entire grid, return numIslands.

Explanation

The algorithm uses Depth-First Search (DFS) to explore connected components. When it encounters a '1' (land), it recursively visits all adjacent '1's, effectively marking the entire island as visited. The counter numIslands keeps track of how many times this process is initiated, representing the number of distinct islands.

Code

#include <vector>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int numIslands = 0;
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();

        function<void(int, int)> dfs = [&](int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
                return;
            }
            grid[i][j] = '0'; // Mark as visited
            dfs(i + 1, j);
            dfs(i - 1, j);
            dfs(i, j + 1);
            dfs(i, j - 1);
        };

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    dfs(i, j);
                }
            }
        }
        return numIslands;
    }
};

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. Each cell is visited at most once.
• Space Complexity: O(M * N) in the worst-case scenario (all cells are connected forming one large island), due to the recursive call stack of the DFS function. In a more realistic scenario with several smaller islands, the space complexity can be significantly lower. A BFS approach would use a queue, also potentially using O(M*N) space in the worst case but often less.