Understanding the Problem
We are given a binary matrix, where each cell contains either 0
or 1
. Our task is to count how many connected components of 1
s exist in this matrix.
A connected component is a group of 1
s that are connected horizontally or vertically. Diagonal connections do not count. Two 1
s are part of the same component if you can reach one from the other by moving up, down, left, or right through other 1
s.
Step-by-Step Solution with Example
step 1: Understand the input
We will be given a 2D array (matrix) of 0s and 1s. Each cell represents either land (1) or water (0).
step 2: Prepare for traversal
We need to track whether a cell has already been visited so that we don’t count the same component more than once. We'll use a separate matrix or a set to mark visited cells.
step 3: Traverse the matrix
Loop through each cell in the matrix. If the cell contains a 1
and has not been visited, that means it’s a new component. We then perform a traversal (DFS or BFS) starting from that cell.
step 4: Use DFS to mark connected 1s
From the current cell, we explore all its 4-directionally adjacent neighbors. For every neighbor that is also 1
and unvisited, we continue the traversal. This way, we mark the entire component as visited.
step 5: Count the components
Every time we start a new DFS from an unvisited 1
, it means we’ve found a new component. So, we increment our count.
step 6: Example
1 1 0 0
0 1 0 1
0 0 0 1
1 0 0 0
Let’s walk through this:
- The group of
1
s at the top-left ((0,0)
, (0,1)
, (1,1)
) form one component.
- The group
(1,3)
, (2,3)
is another component.
- The cell
(3,0)
is a standalone 1
, which is its own component.
So the total number of components is 3.
Edge Cases
Empty matrix
If the matrix is empty or has no rows/columns, there are no components. Return 0
.
All zeros
If every cell is 0
, then again, no components exist. Output is 0
.
Single cell matrix
If the matrix is [[1]]
, output is 1
. If it is [[0]]
, output is 0
.
Diagonal connections
If 1
s are connected only diagonally, they are not considered part of the same component.
Finally
This problem helps build intuition for graph traversal using DFS or BFS. It also teaches how to treat a 2D matrix as a graph, where each cell is a node. By following a systematic approach — identifying a fresh 1
, traversing its full component, and marking visited nodes — we ensure accurate counting and avoid revisiting nodes. Always consider edge cases to make the solution complete and robust.
Comments
Loading comments...