Count Islands in a Grid
Company: Generalmotors
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given an `m x n` grid where each cell is either land (`1`) or water (`0`), return the number of islands.
An island is a group of land cells connected only horizontally or vertically. Diagonal connections do not count as connected.
Implement a function such as:
```python
def count_islands(grid: list[list[int]]) -> int:
pass
```
Requirements:
- The grid may be empty.
- You may mutate the grid if you document that choice, or use a separate visited structure.
- Write test cases that would catch common bugs, especially incorrectly treating diagonal land cells as connected.
Quick Answer: This question evaluates skills in graph traversal and grid connectivity detection, testing competency in reasoning about adjacency, state management, and edge-case handling such as empty grids and the exclusion of diagonal connections.