Connected Components in Binary Image (Islands)
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×N of the grid are at most 50×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:
grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","1"], ["0","0","0","1","1"] ]
2
There are two distinct connected components of '1's in the grid.
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.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.