Katkat
Back

Count connected components in a binary grid

CrowdstrikeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a 2D grid as a graph and use graph traversal algorithms like DFS or BFS to count distinct connected components.

Problem Statement

Given a 2D grid of size m x n consisting of binary values: 1 (representing land) and 0 (representing water), return the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Function Signature

def count_islands(grid: List[List[str]]) -> int:

Constraints

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

Examples

Example 1: Input: grid = [["1","1","0"],["1","1","0"],["0","0","1"]] Output: 2 Explanation: The top-left cluster is one island, and the bottom-right '1' is the second island.

Example 2: Input: grid = [["1","1","1"],["0","1","0"],["1","1","1"]] Output: 1 Explanation: All '1's are connected.

Edge Cases

  • An empty grid or a grid with no '1's should return 0.
  • A grid completely filled with '1's should return 1.

Hints

Hint 1

Consider the grid as a graph where each cell with a '1' is a node, and adjacent '1's share an edge.

Hint 2

You can iterate through each cell; whenever you encounter a '1', trigger a traversal (DFS or BFS) to visit all reachable '1's in that island.

Hint 3

To avoid infinite loops and double counting, 'mark' visited land cells, either by using a boolean matrix or by modifying the grid in-place (e.g., changing '1' to '0').

Follow-up questions

  • How would you modify your solution if diagonal connections were also considered part of an island?
  • What is the time and space complexity of your solution, and how would you optimize the space if you are not allowed to modify the input grid?
  • If the grid is extremely large (e.g., petabytes of data) and cannot fit in memory, how would you approach counting the connected components?