Number of Islands

Count connected groups of land in a grid.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Number of Islands: Count each unseen land seed once, then erase its entire four-neighbor component with DFS.

Input and goalCount connected groups of land in a grid.

Start island 1Row-major scan reaches unseen land (0,0): increment islands to 1, change it to 0, and initialize stack=[(0,0)].

0DFS top100010110011011

input4x4 grid; 4-neighbor land onlystack[(0,0)]islands1

Recognize it

The task asks for connected groups in a binary grid under four-direction adjacency, so every unseen land cell identifies exactly one not-yet-counted component.

Keep true

Before the scan advances, every visited land cell has been changed to 0; each stack contains only cells from the current island, and each completed island can never be counted again.

Reuse it

For regions, blobs, and connected-component problems, scan for unseen seeds, count seeds rather than cells, and exhaustively mark each seed’s reachable component before continuing.

Pattern: DFS from each unseen land cell.

Simple idea: Each unseen land cell starts one new island. DFS changes every connected land cell to water, so that island is never counted again.

def num_islands(grid: list[list[str]]) -> int:
   islands = 0

   for row in range(len(grid)):
      for col in range(len(grid[0])):
         if grid[row][col] != "1":
            continue

         islands += 1
         grid[row][col] = "0"
         stack = [(row, col)]
         while stack:
            current_row, current_col = stack.pop()
            for row_step, col_step in ((1, 0), (-1, 0), (0, 1), (0, -1)):
               new_row = current_row + row_step
               new_col = current_col + col_step
               if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]):
                  if grid[new_row][new_col] == "1":
                     grid[new_row][new_col] = "0"
                     stack.append((new_row, new_col))

   return islands

Cost: $O(rows\times cols)$ time and space.