Last Updated: 8 Jan, 2022

Special Cells in Binary Matrix

Easy

Asked in companies

Solve now

Problem statement

Ninja is observing a Binary matrix of size N * M . A Binary Matrix is made up of only 0’s and 1’s. Ninja wants to know the number of special cells in the matrix. The conditions of a cell to be a special cell are:

The value of M[i][j] should be 1.
All other cells of row i should be 0.
All other cells of column j should be 0.

You are given the matrix ‘MAT’ of size N * M. Your task is to find the number of special cells in the given matrix.

For Example

For the matrix :
  1  0  0
  0  0  0
  0  1  0

The Answer will be 2 as cell (0,0) and (2,1) are special.(Indexing is 0 based).

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers,' N’ and ‘M’ denoting the number of rows and columns.

The next line of each test case has ‘N’ lines that have M values corresponding to the matrix ‘MAT’.

Output Format:

For each test case, print an integer corresponding to the number of special cells in the matrix.

 Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 1000.
1 <= M <= 1000.

Time limit: 1 sec

Solve now

Approaches

01 Approach

If we observe the special cells of the matrix, we will find a pattern that the row sum and column sum of the special cell must be 1 as it should not contain any other ‘1’ in the row or the column.

In this approach, we will iterate each cell of the matrix. Whenever we encounter a value MAT[i][j] as 1, we will simply traverse the ith row and jth column and calculate their sum. If both row sum and column sum are equal to 1, we will increment our ‘ANS’ and at the end, we will return the value of ‘ANS’.

Algorithm:

Declare a variable ‘ANS’ to store the number of special cells.
Set ‘ANS’ as 0.
For i in range 0 to N-1:
- For j in range 0 to M-1:
  - If MAT[i][j] is equal to 1:
    - Check for the entire ith row and jth column.
    - Set ‘ROWSUM’ as 0.
    - For k in range 0 to N-1:
      - Set ‘ROWSUM’ as ROWSUM + MAT[k][j].
    - Set ‘COLSUM’ as 0.
    - For k in range 0 to M-1:
      - Set ‘COLSUM’ as COLSUM + MAT[i]kj].
    - If ROWSUM == 1 and COLSUM == 1:
      - Found a special cell.
      - Set ‘ANS’ as ‘ANS’ + 1.
Return ‘ANS’.

Solve now

02 Approach

We will optimize the above brute force by storing the sum of ROWS and COLUMN

So, we will prepare two arrays ‘ROWSUM’ and ‘COLSUM’ to store the sum of the ith row and ‘i’th column. After that, we will iterate over each cell of the matrix and if the cell has value 1 and ‘ROWSUM’ and ‘COLSUM’ is also 1, we found a special cell. We will increment our final answer.

Algorithm:

Declare two arrays ‘ROWSUM’ and ‘COLSUM’ of size N and M respectively.
Set all values of arrays as 0.
Declare a variable ‘ANS’ to store the number of special cells.
Set ‘ANS’ as 0.
For i in range 0 to N-1:
- For j in range 0 to M-1:
  - Set ROWSUM[i] as ROWSUM[i] + MAT[i][j].
  - Set COLSUM[j] as COLSUM[j] + MAT[i][j].
For i in range 0 to N-1:
- For j in range 0 to M-1:
  - If MAT[i][j] == 1 and ROWSUM[i]==1 and COLSUM[j]==1:
    - Found a special cell.
    - Set ‘ANS’ as ‘ANS’ + 1.

Return ‘ANS’.

Solve now