200. Number of Islands

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 200

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

...

Approach & Solution Steps

• Union-Find on grid cells — O(n m α(nm)).
• Optimal — DFS mark visited 0 or separate seen — O(nm) time, O(nm) recursion stack worst case.

Optimal JS Solution

function numIslands(grid) {
  if (grid.length === 0) {
    return 0;
  }
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function flood(row, col) {
    if (row < 0 || col < 0 || row >= rows || col >= cols) {
      return;
    }
    if (grid[row][col] !== '1') {
      return;
    }
    grid[row][col] = '0';
    flood(row + 1, col);
    flood(row - 1, col);
    flood(row, col + 1);
    flood(row, col - 1);
  }

  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] === '1') {
        count += 1;
        flood(row, col);
      }
    }
  }
  return count;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.