Count Grid Islands That Never Touch the Border
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a rectangular grid in which `0` marks a land cell and `1` marks a water cell. An island is a maximal group of land cells connected horizontally or vertically. An island is *enclosed* when water surrounds it on every side inside the grid, that is, when none of its cells lies on the border of the grid. Return the number of enclosed islands.
### Function Signature
```python
def count_enclosed_islands(grid: list[list[int]]) -> int:
```
### Rules
- Cells `(r, c)` and `(r2, c2)` are adjacent when they share an edge: `abs(r - r2) + abs(c - c2) == 1`. Diagonal cells are not adjacent, so land cells that touch only at a corner belong to different islands.
- With `m` rows and `n` columns, the border cells are those in row `0`, row `m - 1`, column `0` or column `n - 1`. The area outside the grid does not count as water: an island with at least one border cell is not enclosed.
- Every enclosed island counts once, whatever its size or shape.
### Constraints
- `1 <= m = len(grid) <= 100` and `1 <= n = len(grid[0]) <= 100`; all rows have the same length.
- Every `grid[r][c]` is `0` or `1`.
- The answer is an integer between `0` and `m * n`.
### Examples
**Example 1**
```text
Input: grid = [[1, 1, 1, 1, 1, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1],
[0, 0, 1, 1, 1, 1]]
Output: 2
```
There are four islands. `{(1, 1), (1, 2), (2, 1)}` and `{(2, 4), (3, 3), (3, 4)}` have no border cell, so they are enclosed. `{(0, 5), (1, 5)}` and `{(4, 0), (4, 1)}` lie on the border.
**Example 2**
```text
Input: grid = [[1, 1, 1, 1],
[1, 0, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 0]]
Output: 2
```
The land cells `(1, 1)`, `(2, 2)` and `(3, 3)` touch only diagonally, so they form three separate islands. `(1, 1)` and `(2, 2)` are enclosed; `(3, 3)` is a border cell.
**Example 3**
```text
Input: grid = [[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 1, 1, 1, 1]]
Output: 0
```
All nine land cells form one ring-shaped island. It reaches the border only through the cell `(3, 4)` in the last column, but that is enough: the island is not enclosed.
Overview: Coding problem on a binary grid where 0 marks land and 1 marks water: count the islands, connected horizontally or vertically, that have no cell on the grid's border. It tests grid traversal, connected components and careful handling of islands that reach the edge through a single cell.
Read the full Snapchat Software Engineer interview experience this question came from
You are given a rectangular grid `grid` with `m` rows and `n` columns. A cell holding `0` is land and a cell holding `1` is water. An island is a maximal group of land cells connected horizontally or vertically. An island is *enclosed* when water surrounds it on every side inside the grid, that is, when none of its cells lies on the border of the grid.
Return the number of enclosed islands.
**Rules**
- Cells `(r, c)` and `(r2, c2)` are adjacent when they share an edge: `abs(r - r2) + abs(c - c2) == 1`. Diagonal cells are not adjacent, so land cells that touch only at a corner belong to different islands.
- The border cells are those in row `0`, row `m - 1`, column `0` or column `n - 1`. The area outside the grid does not count as water: an island with at least one border cell is not enclosed.
- Every enclosed island counts once, whatever its size or shape.
**Constraints**
- `1 <= m = len(grid) <= 100` and `1 <= n = len(grid[0]) <= 100`; all rows have the same length.
- Every `grid[r][c]` is `0` or `1`.
- The answer is an integer between `0` and `m * n`. Because `m * n <= 10,000`, it never exceeds 2^31 - 1, so a 32-bit `int` is enough in every language.
**Example 1**
```text
Input: grid = [[1, 1, 1, 1, 1, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1],
[0, 0, 1, 1, 1, 1]]
Output: 2
```
There are four islands. `{(1, 1), (1, 2), (2, 1)}` and `{(2, 4), (3, 3), (3, 4)}` have no border cell, so they are enclosed. `{(0, 5), (1, 5)}` and `{(4, 0), (4, 1)}` lie on the border.
**Example 2**
```text
Input: grid = [[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 0],
[1, 1, 1, 1, 1]]
Output: 0
```
All nine land cells form one ring-shaped island. It reaches the border only through the cell `(3, 4)` in the last column, but that is enough: the island is not enclosed.
Constraints
- 1 <= m = len(grid) <= 100
- 1 <= n = len(grid[0]) <= 100, and all rows have the same length
- Every grid[r][c] is 0 (land) or 1 (water)
- The answer is an integer between 0 and m * n (at most 10,000, so it fits in a 32-bit int)
Examples
Input: ([[0]],)
Expected Output: 0
Explanation: Minimum 1x1 grid of land: the only cell is a border cell, so its island is not enclosed.
Input: ([[1]],)
Expected Output: 0
Explanation: Minimum 1x1 grid of water: there is no land at all.
Hints
- Only edge-sharing neighbours are connected: land cells that meet only at a corner belong to different islands.
- One cell in row 0, row m - 1, column 0 or column n - 1 disqualifies its entire island, so decide an island's status only after you have accounted for all of its cells.
- A single island can be a winding path of thousands of cells, so make sure your traversal copes with that length.