Count Islands of Connected Land Cells in a Binary Grid

You are given an m x n grid where 1 is land and 0 is water. An island is a maximal group of land cells connected horizontally or vertically. Return the number of islands in the grid.

Function Signature

def count_islands(grid: list[list[int]]) -> int:

Rules

• Two land cells belong to the same island exactly when one can be reached from the other by moving up, down, left or right through land cells. Diagonal contact does not connect cells.
• Every position outside the grid is water.
• Return 0 if the grid has no land.

Constraints

• 1 <= m, n <= 300, where m = len(grid) and len(grid[i]) == n for every row i
• Every cell is 0 or 1.
• A single island can contain all m * n cells, and the answer is at most m * n.

Examples

Example 1

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

The islands are {(0, 0), (1, 0)}, {(0, 2), (0, 3), (1, 3)}, {(2, 1), (3, 0), (3, 1)} and {(3, 3)}. Cells (1, 0) and (2, 1) touch only diagonally, so they are in different islands.

Example 2

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

The middle column connects the top and bottom rows into one island.

Example 3

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