Special Cells in Binary Matrix

Easy
0/40
Average time to solve is 30m
3 upvotes
Asked in companies
UberOracle

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 3
1 0 0
0 0 0
0 1 0
4 3
1 0 0
0 0 1
0 0 0
0 1 1
Sample Output 1:
2
1
Explanation of sample input 1:
For the first test case,
There are two special cells having index (0,0) and (2,1).Hence, the answer is 2.

For the second test case:
There is only one cell that is special having an index (0,0). Hence, the answer is 1.
Hence the answer is 3.
Sample Input 2:
2
4 4
0 1 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 1 
4 3
0 1 0 
0 0 1 
0 1 0 
0 0 0
Sample Output 2:
2
1
Hint

Check for each cell whose value is MAT[i][j] = 1. Check whether the cell is special or not.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N*M *(N+M) ), where ‘N’ and ‘M’ represent the rows and columns of the matrix.

 

In this approach, we are checking each cell, and if the MAT[i][j] for the cell is 1 we are again checking the whole row and column which takes O(M+N) time. Hence, the overall time complexity is O(M*N*(M+N)).

Space Complexity

O( 1).

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Special Cells in Binary Matrix
Full screen
Console