Number of Islands

Problem

Mapping services need to count discrete landmasses in satellite imagery. Given a 2D grid where '1' represents land and '0' represents water, count the number of islands. An island is a group of adjacent '1' cells connected horizontally or vertically, surrounded by water.

grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0'],
] → 1
 
grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1'],
] → 3

Solution

Approach: Grid DFS with in-place sinking (connected-component count on an implicit graph).

Treat the grid as an implicit graph where every '1' is a node and adjacent '1' cells share an edge. Counting islands is just counting connected components. The outer double loop scans every cell; when it finds a '1' that has not been sunk yet, that cell belongs to a brand-new island, so it launches a DFS and bumps the counter by one. The DFS recurses into all four neighbors and, crucially, sets grid[row][col] = '0' the moment it enters a land cell. That mutation doubles as the visited mark - a sunk cell fails the != '1' guard, so recursion never re-enters it and the count never double-tallies the same landmass. The two guards at the top of dfs (out-of-bounds, then non-land) are what keep the recursion safely inside the grid. Trace the three-islands example - the first DFS from (0,0) floods the whole top-left 2x2 block to water in one launch, so when the scan later reaches those cells they are already '0' and skipped; only the next fresh '1' (the middle island) triggers launch two.

Edge cases: Empty grid returns 0 via the not grid guard; an all-water grid never launches DFS; a single '1' is one island. A checkerboard makes every land cell its own island since no two share an edge.

Complexity: O(m * n) time, O(m * n) space - each cell is visited once, and a snake-shaped island can drive recursion depth to the full cell count.