Count Islands of Horizontally or Vertically Connected Land in a Grid
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a rectangular grid in which `1` marks land and `0` marks 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 when a path of land cells joins them, each step moving one cell up, down, left or right.
- Cells that touch only at a corner are not connected.
- Every cell outside the grid is water.
- Coordinates in the examples are written `(row, column)`, counted from 0.
### Constraints
- `1 <= len(grid) <= 300` and `1 <= len(grid[i]) <= 300`, with all rows the same length
- every `grid[i][j]` is `0` or `1`
### Examples
**Example 1**
```text
Input: grid = [[1, 1, 0, 1],
[0, 1, 0, 1],
[1, 0, 0, 0],
[1, 0, 1, 1]]
Output: 4
```
The islands are {(0, 0), (0, 1), (1, 1)}, {(0, 3), (1, 3)}, {(2, 0), (3, 0)} and {(3, 2), (3, 3)}. The cells (1, 1) and (2, 0) touch only at a corner, so they belong to different islands.
**Example 2**
```text
Input: grid = [[1, 1, 1],
[1, 0, 1],
[1, 1, 1]]
Output: 1
```
The ring of land is one island; the water cell it encloses does not split it.
**Example 3**
```text
Input: grid = [[0, 0],
[0, 0]]
Output: 0
```
Overview: Count the islands in a grid of land and water cells, where land cells connect horizontally or vertically but not diagonally. An onsite coding problem that tests grid traversal, connected components, and correct handling of enclosed water and of large grids that are entirely land.
Read the full Oracle Software Engineer interview experience this question came from