Sizes of 4-Connected Foreground Regions in a Binary Image, in Scan Order

An image is represented by a rectangular binary matrix image with m rows and n columns. A cell holding 1 is a foreground pixel, and a cell holding 0 is a background pixel.

Two foreground pixels belong to the same region when they are adjacent horizontally or vertically. Pixels that touch only diagonally are not adjacent. A region is a maximal set of foreground pixels connected through such adjacencies, and its size is the number of foreground pixels it contains.

Return the size of every region, in the order the regions are first encountered while scanning the image from top to bottom and, within each row, from left to right.

Function Signature

def get_region_sizes(image: list[list[int]]) -> list[int]:

Rules

• The scan visits cells in row-major order: (0, 0), (0, 1), ..., (0, n - 1), (1, 0), ..., (m - 1, n - 1), where (r, c) is row r, column c.
• A region is encountered at the first scanned cell that belongs to it. Regions are listed in the order of those first cells, not by size and not by their leftmost column.
• Every foreground pixel belongs to exactly one region, so the returned sizes sum to the number of 1 cells.
• If the image contains no foreground pixel, return an empty list.

Constraints

• 1 <= m <= 1000 and 1 <= n <= 1000, where m = len(image) and len(image[r]) == n for every row r
• Every cell is 0 or 1.
• The image has at most 1,000,000 pixels, so every region size fits in a 32-bit signed integer.
• A single region can contain every pixel of the image, up to 1,000,000 pixels, and must still be measured correctly.

Examples

Example 1

Input: image = [[0, 1, 1, 0, 0], [0, 0, 1, 0, 1], [1, 0, 0, 0, 1], [1, 0, 1, 1, 1], [1, 1, 0, 0, 0]]
Output: [3, 5, 4]

The scan first reaches (0, 1), whose region is (0, 1), (0, 2), (1, 2): size 3. It next reaches (1, 4), whose region is (1, 4), (2, 4), (3, 4), (3, 3), (3, 2): size 5. The last region starts at (2, 0) and is (2, 0), (3, 0), (4, 0), (4, 1): size 4. The size-5 region is listed before the size-4 region because (1, 4) is scanned before (2, 0).

Example 2

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

The five foreground pixels touch only at corners, so each one is a region of size 1.

Example 3

Input: image = [[0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 0, 1], [0, 1, 1, 1]]
Output: [10]

All ten foreground pixels form one region that wraps around the image. It is first reached at (0, 2). The pixel (1, 0) connects to it through the bottom row, so it does not start a new region.