Count Islands of Connected Land Cells in a Binary Grid
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
Input: grid = [
[0, 0],
[0, 0]
]
Output: 0
```
Overview: A classic grid coding problem asking you to count the islands formed by horizontally or vertically connected land cells in a binary grid. It tests grid traversal, connected-component counting, and careful handling of grid boundaries and already visited cells.
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.
Implement `count_islands(grid)`. It receives the grid as a list of `m` rows, each a list of `n` integers, and returns the number of islands as an integer.
### 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`.
The answer is at most `300 * 300 = 90,000`, so it never exceeds `2^31 - 1` and fits in a 32-bit `int` in every language.
### Examples
**Example 1**
```text
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**
```text
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.
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
Input: ([[1, 0, 1, 1], [1, 0, 0, 1], [0, 1, 0, 0], [1, 1, 0, 1]],)
Expected Output: 4
Explanation: Source example 1: four islands; (1, 0) and (2, 1) touch only diagonally.
Input: ([[1, 1, 1], [0, 1, 0], [1, 1, 1]],)
Expected Output: 1
Explanation: Source example 2: the middle column joins the top and bottom rows.
Hints
- Only up, down, left and right moves join land cells; two land cells that touch only at a corner are in the same island only if some orthogonal path of land links them.
- Positions outside the grid are water, so a land cell on the border or in a corner has fewer than four possible land neighbors.
- One island can cover all 90,000 cells of a 300 x 300 grid, so whatever you use to walk an island must cope with a component of that size.