Katkat
Back

Count the Separate Land Regions in a Binary Grid Map

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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