Katkat
Back

Count Regions in a Binary Grid

IllumioSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to navigate a 2D grid and identify connected components using graph traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS).

Problem Statement

Given an m x n binary grid grid where 1 represents land and 0 represents water, a region is defined as a group of 1s connected 4-directionally (horizontally or vertically). Write a function to return the total number of distinct regions in the grid.

Function Signature

def count_regions(grid: list[list[int]]) -> int:

Examples

Example 1: Input:

grid = [
  [1, 1, 0, 0],
  [1, 1, 0, 0],
  [0, 0, 1, 0],
  [0, 0, 0, 1]
]

Output: 3 Explanation: There are two regions of connected 1s on the top left and two individual 1s on the bottom right diagonal.

Example 2: Input:

grid = [
  [1, 0, 1],
  [0, 1, 0],
  [1, 0, 1]
]

Output: 5

Constraints

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

Edge Cases

  • An empty grid or a grid with no 1s.
  • A grid filled entirely with 1s.
  • Grids with a single cell.

Hints

Hint 1

You can treat the grid as an undirected graph where each '1' cell is a node, and adjacent '1' cells share an edge.

Hint 2

Iterate through every cell in the grid; when you encounter a '1', trigger a traversal to mark all connected '1's as visited.

Hint 3

To save space, you can modify the input grid directly to '0' once a cell is visited, rather than using an auxiliary visited set.

Follow-up questions

  • How would your approach change if diagonal connections were also considered part of a region?
  • What is the time and space complexity of your solution in terms of m and n?
  • If the grid were too large to fit into memory, how would you approach counting regions using a streaming or block-based strategy?