Count Four-Neighbor Islands in a Binary Matrix
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Given a two-dimensional binary matrix, return the number of islands. An island is a connected component of cells containing `1`. Cells connect only through a shared edge: up, down, left, or right. Diagonal contact does not connect islands.
### Input and Output
- Input: a rectangular matrix containing only `0` and `1`.
- Output: one integer, the number of islands.
- For this practice version, an empty matrix or a matrix with no land has answer `0`.
### Example
```text
grid = [
[1, 1, 0],
[0, 1, 0],
[1, 0, 1]
]
answer = 3
```
The connected cells at the upper left form one island; the two isolated cells in the last row form two more.
### Discussion Extension
How would the task change if matrix rows arrived one at a time? The source asks this as a follow-up but supplies no streaming-call interface; the function above receives the complete matrix.
Overview: Count four-neighbor islands in a binary matrix and consider the connectivity state needed when rows arrive as a stream.
Read the full Amazon Software Engineer interview experience this question came from
Given a two-dimensional binary matrix, return the number of islands. An island is a connected component of cells containing `1`. Cells connect only through a shared edge: up, down, left, or right. Diagonal contact does not connect islands.
### Input and Output
- Input: a rectangular matrix containing only `0` and `1`.
- Output: one integer, the number of islands.
- For this practice version, an empty matrix or a matrix with no land has answer `0`.
### Example
```text
grid = [
[1, 1, 0],
[0, 1, 0],
[1, 0, 1]
]
answer = 3
```
The connected cells at the upper left form one island; the two isolated cells in the last row form two more.
### Discussion Extension
How would the task change if matrix rows arrived one at a time? The source asks this as a follow-up but supplies no streaming-call interface; the function above receives the complete matrix.
Constraints
- grid is a finite rectangular matrix containing only integer 0 and 1; an empty matrix is allowed.
- Only up, down, left, and right adjacency connects land cells.
- No numeric row or column bound is supplied.
Examples
Input: ([[1, 1, 0], [0, 1, 0], [1, 0, 1]],)
Expected Output: 3
Explanation: The three-cell upper-left component and two isolated land cells form three islands.
Input: ([[1, 0], [0, 1]],)
Expected Output: 2
Explanation: Diagonal contact does not join two land cells.
Hints
- Only cells sharing an edge can belong to the same island.
- An empty matrix or one without land returns 0.