200. Number of Islands

At a Glance

Topic: graphs
Pattern: DFS / Backtracking (grid DFS) / BFS / Union-Find
Difficulty: Medium
Companies: Amazon, Meta, Microsoft, Google, Bloomberg
Frequency: Very High
LeetCode: 200

Problem (one-liner)

Count connected components of '1' cells in a binary grid (4-directionally adjacent).

Recognition Cues

Grid connectivity
Flood fill / island counting
Each 1 starts DFS/BFS if unseen

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

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 Solution

Go

func numIslands(grid [][]byte) int {
	if len(grid) == 0 {
		return 0
	}
	rows := len(grid)
	cols := len(grid[0])
	count := 0

	var flood func(row int, col int)
	flood = func(row int, col int) {
		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 row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if grid[row][col] == '1' {
				count++
				flood(row, col)
			}
		}
	}
	return count
}

JavaScript

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;
}