Quick Overview

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.

Count Connected Land Regions

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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:** ```text 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'`.

Overview: 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 grid representing a map. Each cell contains either '1' for land or '0' for water. A land region is a group of land cells connected horizontally or vertically. Diagonal cells are not connected. Return the number of distinct connected land regions in the grid.

Constraints

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

Examples

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)

Expected Output: 3

Explanation: There are three separate groups of connected land cells.

Input: ([['0']],)

Expected Output: 0

Explanation: A single water cell contains no land regions.

Hints

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

Loading coding console...