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
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…
46+ registered 