Count Islands in a Grid

Implement count_islands(grid: list[list[int]]) -> int.

The rectangular grid contains water cells 0 and land cells 1. An island is a maximal group of land cells connected through shared horizontal or vertical edges. Return the number of islands.

Input Domain

• 0 <= len(grid) <= 2,000.
• If the grid is nonempty, all rows have the same length.
• The grid contains at most 1,000,000 cells.
• Every cell is exactly 0 or 1.

Output Rules

• Diagonal contact does not connect two land cells.
• Return 0 for an empty grid, empty rows, or a grid containing only water.
• The input may be modified by the implementation.

Constraints

• Target time is O(rows * columns).
• Avoid recursion whose call depth can grow with the number of cells.

Examples

Example 1

Input: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]

Output: 2

Example 2

Input: grid = [[0,0],[0,0]]

Output: 0

Hint: Consume one connected component at a time

When an unvisited land cell is found, traverse every land cell reachable from it before continuing the grid scan.