Find Every Island in a Grid and Measure Its Boundary with Water

You are given an m x n grid where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically. This is a variant of island counting: besides finding the islands, measure each island's boundary with water, which is the number of unit-length cell sides where a cell of the island meets water.

Return the boundary length of every island, one value per island, so the length of the result is the number of islands.

Function Signature

def island_boundaries(grid: list[list[int]]) -> list[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 counts as water, so a land cell's side on the border of the grid is part of the boundary.
• An island's boundary length is the number of pairs (land cell of the island, one of its four sides) where the neighbor across that side is water or outside the grid. Water completely enclosed by an island counts like any other water.
• Order the result by each island's first cell in row-major order: for each island, take its cell with the smallest row index, breaking ties by the smallest column index, and sort the islands by that cell's (row, column).
• If the grid has no land, return an empty list.

Constraints

• 1 <= m, n <= 500, 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. Every boundary length is at most 4 * m * n = 1,000,000, which fits in a 32-bit signed integer.

Examples

Example 1

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

The first island is cells (0, 0), (0, 1) and (1, 0), with boundary 8. The second island is cells (1, 3), (2, 1), (2, 2) and (2, 3), with boundary 10; its first cell in row-major order is (1, 3). Cells (1, 0) and (2, 1) touch only diagonally, so they belong to different islands.

Example 2

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

The eight land cells form one island. Its outer boundary has 12 sides, and the enclosed water cell adds 4 more.

Example 3

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