37. Number of Islands

Given an m x n 2D binary 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.

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

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

Problem Breakdown:

1. Iterate through every cell in the grid. When we find a '1' (land) that has not been visited, it is the start of a new island.

• count = 0
  for i in range(len(grid)):
      for j in range(len(grid[0])):
          if grid[i][j] == '1':

2. Increment the island count and use DFS/BFS to mark all connected land cells as visited (change '1' to '0').

•             count += 1
              dfs(grid, i, j)

3. The DFS function checks boundaries and if the cell is land. If valid, mark it as visited and recurse in all four directions.

• def dfs(grid, i, j):
      if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
          return
      grid[i][j] = '0'
      dfs(grid, i+1, j)
      dfs(grid, i-1, j)
      dfs(grid, i, j+1)
      dfs(grid, i, j-1)

4. After processing the entire grid, return the island count.

• return count

Summary:

Scan the grid for unvisited land cells. Each unvisited '1' starts a new island. Use DFS to flood-fill and mark all connected land as visited. Count how many times we initiate a new DFS.

Time and Space Complexity:

Time Complexity: O(m * n) - we visit each cell at most once.

Space Complexity: O(m * n) - recursion stack in worst case (all land).

Python Solution:

def numIslands(grid):
    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

JavaScript Solution:

var numIslands = function(grid) {
    const dfs = (i, j) => {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') return;
        grid[i][j] = '0';
        dfs(i+1, j);
        dfs(i-1, j);
        dfs(i, j+1);
        dfs(i, j-1);
    };
    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
};

Java Solution:

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
}