Find Every Island in a Grid and Measure Its Boundary with Water
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: grid = [
[0, 0, 0],
[0, 0, 0]
]
Output: []
```
Overview: A grid coding problem that asks you to find every island of land cells and report the length of each island's boundary with water, including enclosed lakes and grid edges. It tests grid traversal, connected components, careful edge counting, and deterministic output ordering.
Read the full Waymo Software Engineer interview experience this question came from
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. Besides finding the islands, measure each island's boundary with water: 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 returned list equals the number of islands.
**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)`, smallest first.
- If the grid has no land, return an empty list.
Every boundary length is at most `4 * m * n = 1,000,000`, so every value fits in a signed 32-bit integer (`int` in Java and C++).
**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.
**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.
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
Input: ([[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1]],)
Expected Output: [8, 10]
Explanation: Source Example 1: the island starting at (0, 0) has boundary 8 and the island whose first cell is (1, 3) has boundary 10; (1, 0) and (2, 1) touch only diagonally.
Input: ([[1, 1, 1], [1, 0, 1], [1, 1, 1]],)
Expected Output: [16]
Explanation: Source Example 2: an eight-cell ring has 12 outer sides plus 4 sides facing the enclosed water cell.
Hints
- The boundary counts cell sides, not neighboring water cells: one water cell, or the outside of the grid, is counted once for every island side it touches.
- Each island is ordered by its smallest (row, column) cell. Think about which cell of an island a top-to-bottom, left-to-right sweep of the grid reaches first.
- A single island can wind through up to 250,000 cells, so make sure exploring one island does not need to nest as deep as the island is long.