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.
Return the number of 4-directionally connected land components.
Constraints
- grid contains 0 water and 1 land
Examples
Input: ([[1, 1, 0], [0, 1, 0], [1, 0, 1]],)
Expected Output: 3
Explanation: Diagonal land is not connected.
Input: ([],)
Expected Output: 0
Explanation: Empty grid.
Input: ([[0, 0]],)
Expected Output: 0
Explanation: No land.
Input: ([[1, 1], [1, 1]],)
Expected Output: 1
Explanation: One island.
Hints
- BFS or DFS from each unvisited land cell.