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).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

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