Sizes of 4-Connected Foreground Regions in a Binary Image, in Scan Order
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given a binary image stored as a matrix of 0s and 1s, return the size of every region of horizontally or vertically connected foreground pixels, ordered by when each region is first reached in a top-to-bottom, left-to-right scan. It tests grid traversal, connected components, and handling a single region that covers up to a million pixels.
Read the full Microsoft Software Engineer interview experience this question came from
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.
Implement `get_region_sizes(image)`, which returns 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.
**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; no returned value can exceed 2^31 - 1.
- A single region can contain every pixel of the image, up to 1,000,000 pixels, and must still be measured correctly.
**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.
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; no returned value can exceed 2^31 - 1.
- A single region can contain every pixel of the image, up to 1,000,000 pixels, and must still be measured correctly.
Examples
Input: ([[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]],)
Expected Output: [3, 5, 4]
Explanation: Source example 1: regions first reached at (0, 1), (1, 4) and (2, 0); the size-5 region precedes the size-4 one by scan order, while sorting by size or a column-major scan would differ.
Input: ([[1, 0, 1], [0, 1, 0], [1, 0, 1]],)
Expected Output: [1, 1, 1, 1, 1]
Explanation: Source example 2: an X pattern whose pixels touch only diagonally, so each pixel is its own size-1 region.
Hints
- A region is reported once, at the first of its cells that the row-major scan reaches; a later cell of a region that has already been reported must not start a new entry.
- Only horizontal and vertical contact joins pixels, and a region can extend to the left of, or wrap back toward, the cell where the scan first meets it.
- A single region may hold all 1,000,000 pixels of a 1000 x 1000 image, so measuring one region must not rely on a nesting depth that grows with the size of the region.