## Approach for Solving

The approach for Solving the problem is:-

- It needs to think in the manner of connected graph problem, as it asks all possible non-empty connected cells, as here we have a binary matrix, in which each cell needs to be treated as vertex and all the surrounding element top, left, right, and the bottom has a virtual edge.
- Now we think of a graph problem, as we need to find a possible non-empty connected cell, which means we have to see the adjacent element of the cell how many are together are non-empty, whenever we go to a particular cell then we have to watch out for all the surrounding elements.
- As seen in the discussion part, we are visiting and mapping with neighbouring elements. Then we got an idea of using the BFS algorithm of the graph.
- So we are using the BFS algorithm for solving the problem, as we have to track the adjacent element upon which we decide total possible connected cells.

## Code

```
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class size_non_empty_cell {
//Class for storing row and column , to store the info of adjacent element
// in the Queue.
static class RowCol{
int row;
int col;
RowCol(int row,int col){
this.row=row;
this.col=col;
}
}
static int bfs(int [][] mat,int row, int col){
int count=0;
Queue<RowCol> q=new LinkedList<>();
// Create row and col , i.e cell of matrix as a node of graph
q.add(new RowCol(row,col));
while(!q.isEmpty()) {
RowCol curr = q.peek();
q.poll();
int curr_row = curr.row;
int curr_col = curr.col;
// Boundary Condition if 2-D matrix not goes out of Index
if (curr_row < 0 || curr_col < 0 || curr_row >= mat.length || curr_col >= mat[0].length) {
continue;
}
// If the cell is already visited just continue not go down
if (mat[curr_row][curr_col] == 0) continue;
if (mat[curr_row][curr_col] == 1) {
// After visit marked it as visited by making the cell as empty as of no use
mat[curr_row][curr_col] = 0;
count++;
}
//Move to the adjacent of the current row and column
// In the direction of Top , Left , right and Bottom.
q.add(new RowCol(curr_row+1,curr_col));
q.add(new RowCol(curr_row-1,curr_col));
q.add(new RowCol(curr_row,curr_col+1));
q.add(new RowCol(curr_row,curr_col-1));
}
return count;
}
static void size_of_non_empty_cell(int [][] mat){
ArrayList<Integer> res=new ArrayList<>();
for(int row=0;row< mat.length;row++){
for(int col=0;col<mat[0].length;col++){
//If non-empty cell is found
if(mat[row][col]==1){
int count=bfs(mat,row,col);
res.add(count);
}
}
}
// Printing added possible connected non-empty cell
for(int x:res){
System.out.print(x+" ");
}
}
public static void main(String[] args){
int [][] mat={{1,1,0,0,0},
{1,1,0,0,0},
{0,0,1,0,1},
{1,0,0,0,0},
{1,1,1,1,1}};
size_of_non_empty_cell(mat);
}
}
```

You can also try this code with Online Java Compiler

Run Code

## Dry-Run

For a better understanding, let’s think more detail and observe with the dry -run of the code by taking an example:-

1 1 0 0 0

1 1 0 0 0

0 0 1 0 1

1 0 0 0 0

1 1 1 1 1

Let’s get with the implementation part:-

- The first start, iterating over the matrix cell, if we found the mat[i][j]==1, as a non-empty cell, then we call the bfs function bypassing the current row and column.
- We treat every cell of the matrix as a node of the graph, for which we make a RowCol class for storing the information of nodes in the Queue which contains info of RowCol with having row number and column number. As for the first, we have mat[0][0]=1, so it gets pushed in the Queue, with row and column.
- Now we treat the non-empty cell as the node and run a while loop and check the boundary condition as the position of the cell within the index range does not go beyond that; as for mat[0][0], we have curr_row=0 and curr_col=0 with pass the boundary condition, then we check if it previously visited, then we return directly, if not then, here also we have mat[0][0]=1, which is not visited. We mark this position mat[0][0]=0 as visited and increment the counter by 1; then, we look up the neighbouring element.
- The neighbouring element directly added , to queue , then we repeat step-3 , under while loop , we have found that , mat[0][1]=1 , then count increase by 1 , then for mat[1][0] , mat [1][1] , in all together element at position (0,0) ,(0,1) ,(1,0) and (1,1) are adjacent and total possible connected is 4 .
- For the best part, we followed the same steps 1 to 4 to get our answer, which came out to be 1, 1, and 6 furthermore.
- Now for the position (2,2), we have no adjacency, so the answer is 1; for the position (2,4) same we have no adjacency

mat[i][j]=mat[i-1][j]

mat[i][j]=mat[i][j-1]

mat[i][j]=mat[i+1][j]

mat[i][j]=mat[i][j+1]

These above all 4 conditions,s not satisfying

- Similarly for the position (3,0) we have adjacency connected with (4,0),(4,1),(4,2),(4,3),(4,4).
- After the complete traversal visiting all the adjacent cells, we print all the answers in the ArrayList.

## Complexity

Talking about the Time complexity of the problem, we are traversing the 2-D matrix. It’s just O(row*Col). For the Space Complexity, we are using RowCol class for storing the element in the Queue, which is noting row*col as we have all elements of the binary matrix as 1, then Space Complexity is O(row*col).

## Frequently Asked Question:

**1). What is Binary Matrix?**

Matrix format in which all the elements will be either 0 or 1.

**2). What is BFS?**

Graph traversal starts from the root node and explores all the neighbouring nodes.

**3). What is Time and Space Complexity?**

Time and Space Complexity for the problem is O(row*col).

## Key TakeAway:

In this blog, we work with 2-D Binary Matrix and learn its meaning, and also the traversal of the graph, which is BFS, which helps us to find the connected node with the non-empty elements. Using this concept of Graph, we solve the problem in Time and Space Complexity is O(row*col).

**Recommended Problem - **__Boundary Traversal Of Binary Tree__

Happy Learning…