Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Explanation of Problem Statement
3.
Approach for Solving
4.
Code
5.
Dry-Run
6.
Complexity
7.
Frequently Asked Question:
8.
Key TakeAway:
Last Updated: Mar 27, 2024

Size of all Connected Non-Empty Cell of Matrix

Author Yogesh
0 upvote

Problem Statement

We have given a binary matrix containing the element 0 or 1. Only we have to find all possible non-empty cells.

Also Read About, Array Implementation of Queue and  Rabin Karp Algorithm

Explanation of Problem Statement

We have given a binary matrix, which states that we have only two elements present in every cell of the matrix as either 0 or 1. Where 0 means an empty cell and 1 represents a non-empty cell. We have to find all possible connected non-empty cell components. 

For two-cell to be called the connected, then we have to see the adjacency in the horizontal or vertical direction as listed below, suppose we are at the ith row and jth col then:-

 

Suppose mat[row][col] is a 2-D binary matrix:-

 

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]

 

Any of the four conditions to be stratified for the matrix cell to be called connected.

 

Now, we have to find all possible adjacency cell elements whose connection with 1’s only, i.e. possible non-empty connected cells.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach for Solving

The approach for Solving the problem is:-

 

  1. 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.
  2. 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.
  3. 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.
  4. 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);
  }
}

 

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:-

  1. 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.
  2. 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.
  3. 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.
  4. 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 .
  5. 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.
  6. 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

 

  1. Similarly for the position (3,0) we have adjacency connected with (4,0),(4,1),(4,2),(4,3),(4,4).
  2. 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…

Previous article
Search in a 2-D Matrix which is sorted row-wise and column-wise.
Next article
Count All Number Of Paths Of A Given Matrix
Live masterclass