Find the size of all Connected Non-Empty Cells of a Matrix in C++

12 May 2025 | 4 min read

Problem Statement:

We are given a binary matrix, which indicates that there will be only two elements present in the matrix either zero (0) or one (1), where a non-empty cell is represented by one (1) and an empty cell by zero (0). Finding every possible connected non-empty cell component is our task. Two cells must be adjacent in either a horizontal or vertical direction for them to be referred to as linked.

For Example:

Input:

mat[][] = {[3,1],[4,1]}

Output:

Input:

mat[][] = {[1,2],[2,1]}

Output:

Algorithm:

Create a queue data structure, and then add a cell with the value cell(mat[i][j] = 1).
Go through the neighboring cells of the inserted cell and perform BFS or DFS on it.
Verify whether there are any boundary conditions, and if the element is now 1, flip it to 0.
Update the size of the linked non-empty cells and mark the visited cell.
Print each side of the obtained connections at the end.

Program 1:

Let us take a C++ program to find the size of all Connected Non-Empty Cells of a Matrix using DFS traversal.

Output:

Find the size of all Connected Non-Empty Cells of a Matrix in C++

Time Complexity:

The time complexity to find the sizes of all connected non-empty cells of a matrix using DFS traversal is O(rs * cs).

Space Complexity:

The space complexity to find the sizes of all connected non-empty cells of a matrix using DFS traversal is O(rs * cs).

Program 2:

Let us take another C++ program to find the size of all Connected Non-Empty Cells of a Matrix using BFS traversal:

Output:

Time Complexity:

The time complexity to find the sizes of all connected non-empty cells of a matrix using BFS traversal is O(rs * cs).

Space Complexity:

The space complexity to find the sizes of all connected non-empty cells of a matrix using BFS traversal is O(rs * cs).

Conclusion:

In summary, we can conclude that both Breadth First Search (BFS) and Depth First Search (DFS) provide effective and efficient solutions with the time and space complexities of O(rs*cs). Here, rs represents the number of rows, and cs represents the number of columns in the matrix for determining the sizes of all connected non-empty cells of a matrix. The decision for choosing between DFS and BFS depends on various factors, such as memory limitations, traversal orders, and problem specifications. After considering all the factors, both approaches are efficient for solving the given problem.

Next TopicShift 2D Grid in C++

← prev next →