Katkat
Back

Count Connected Land Regions

eBaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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'.