Count the Separate Land Regions in a Binary Grid Map
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a rectangular map as a grid of cells, where `1` marks land and `0` marks water. Two land cells belong to the same region when they share an edge (up, down, left or right); cells that touch only at a corner are not connected. Return the number of separate land regions on the map.
### Function Signature
```python
def count_land_regions(grid: list[list[int]]) -> int:
```
### Rules
- A region is a maximal set of land cells in which every cell can reach every other by stepping between edge-adjacent land cells.
- Everything outside the grid counts as water.
- A grid with no land cells has 0 regions.
### Constraints
- `1 <= len(grid) <= 300`
- `1 <= len(grid[0]) <= 300`, and every row has the same length
- Every cell is `0` or `1`
- The grid has at most 90,000 cells, and a single region may cover all of them.
### Examples
**Example 1**
```
grid = [[1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, 1, 1],
[0, 0, 0, 0]]
output = 2
```
The three land cells in the top-left corner form one region, and the three on the right form another.
**Example 2**
```
grid = [[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]
output = 5
```
Every land cell touches the others only at corners, so each is its own region.
**Example 3**
```
grid = [[0, 0],
[0, 0]]
output = 0
```
Overview: A coding exercise that counts the separate land regions in a grid map of land and water cells, where land cells connect only through shared edges. It tests systematic exploration of a two-dimensional grid, correct neighbor handling at borders and corners, and scaling to large grids where one region may cover everything.
Read the full Microsoft Software Engineer interview experience this question came from