Connected Components in Binary Image (Islands)

mediumPROGraphsGraphs, Matrix, DFS/BFSCV - DSA

In image segmentation and feature extraction, counting distinct foreground objects requires identifying connected components.

You are given a 2D binary grid (matrix) where '1' represents land (foreground pixel) and '0' represents water (background pixel). An "island" is defined as a maximal group of connected '1's, connected horizontally or vertically (4-directionally).

Your task is to find the total number of disjoint islands (connected components) present in the grid. You must modify the grid in place to keep track of visited land pixels (e.g., by changing '1's to a placeholder value) to ensure each component is counted exactly once.

Constraints:

The grid contains only '1's (land) and '0's (water).
The dimensions $M \times N$ of the grid are at most $50 \times 50$ .

About Topic: This problem directly implements the core logic required for connectivity analysis in pipelines like the Canny Edge Detector, which use BFS or DFS to link local responses into coherent features or edges. This technique is a fundamental step in converting raw pixel data into discrete objects for further classification or analysis.

Example

Input

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

Output

Reasoning

There are two distinct connected components of '1's in the grid.

More from CV - DSA

Concept primerPREVIEW

1. Background Knowledge

Connected components in binary images are maximal groups of foreground pixels ('1's) that are 4-directionally connected (up, down, left, right; no diagonals). This is a fundamental concept in computer vision for image segmentation, object detection, and feature extraction, as seen in pipelines like Canny edge detection where local responses are grouped into coherent structures.

Prerequisites:

2D grid traversal (nested loops over rows/columns).
Graph theory basics: pixels as nodes, edges between 4-neighbors if both are '1'.
Recursion or queue data structures for traversal.
In-place modification to mark visited pixels (avoids extra space for visited set).

2. Algorithm Approach

The standard approach uses Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse and mark each connected component:

DFS: Recursive stack-based exploration (fits small grids ≤50×50).
BFS: Queue-based level-order traversal.
Raster-scan labeling: Two-pass methods assign provisional labels then resolve equivalences (more complex, used in optimized/large-scale variants).

For this problem, DFS/BFS with in-place marking ('1' → '0' or 'X') is optimal due to small constraints and no need for labeling (just counting).

Approach	Pros	Cons
DFS	Simple recursion, low space	Stack overflow risk (rare for 50×50)
BFS	No recursion depth issues	Slightly more space (queue)
Labeling	Extracts components fully	Overkill for counting only

3. Step-by-Step Strategy

Iterate over all cells: Use nested loops (for i in 0..M-1, for j in 0..N-1).
Check for unvisited land: If grid[i][j] == '1', increment island count and start traversal.
Traverse component (DFS or BFS):

Mark current cell as visited (grid[i][j] = '0').
Explore 4 neighbors: up (i-1,j), down (i+1,j), left (i,j-1), right (i,j+1).
Recur/enqueue only if neighbor is valid bounds, '1', and unvisited.

Return total count after checking all cells.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results