Coding questions · eBay

Count Connected Land Regions

This question evaluates understanding of graph connectivity and grid traversal, specifically the detection of connected components within a 2D matrix. It is commonly asked to assess algorithmic problem-solving, efficiency and handling of matrix-based data structures; it belongs to the Coding & Algorithms domain and tests practical implementation skills alongside conceptual understanding of graph-related complexity under the given input constraints.

You are given an m x n 2D grid representing a map. Each cell is either land ('1') or water ('0'). A land region is formed by connecting adjacent land cells horizontally or vertically. Diagonal connections do not count.

Write a function that returns the number of distinct connected land regions in the grid.

Input:

grid: a 2D array of characters, where each value is either '1' or '0'.

Output:

An integer representing the number of connected land regions.

Example:

Input:
grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

Output: 3

Constraints:

1 <= m, n <= 300
grid[i][j] is either '0' or '1'.

Count Connected Land Regions

Hints

Treat each land cell as a node in a graph, where edges exist only in the four cardinal directions.
Whenever you find an unvisited land cell, run BFS or DFS from it to mark the entire region before continuing.