Tutorialspoint.dev

Unique cells in a binary matrix

Given a matrix of size n x m consisting of 0’s and 1’s.We need to find number of unique cells with value 1 such that corresponding entire row and entire column does not have another 1.Return the number of unique cells.

Examples:

Input : mat[][] = {0, 1, 0, 0
                   0, 0, 1, 0
                   1, 0, 0, 1}
Answer : 2
The two 1s that are unique
in their rows and columns
are highlighted.

Input : mat[][] = { 
{0, 0, 0, 0, 0, 0, 1}
{0, 1, 0, 0, 0, 0, 0}
{0, 0, 0, 0, 0, 1, 0}
{1, 0, 0, 0, 0, 0, 0}
{0, 0, 1, 0, 0, 0, 1}
Output : 3



Method 1- Brute Force Approach
In this approach, we are going to check for each cell with value 1 whether the corresponding rows
satisfy our requirement. We will check in corresponding rows and columns of each cell with value 1.

C++

// C++ program to count unique cells in 
// a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
  
// Returns true if mat[i][j] is unique
bool isUnique(int mat[][MAX], int i, int j, 
                              int n, int m)
{
    // checking in row calculating sumrow
    // will be moving  column wise
    int sumrow = 0;
    for (int k = 0; k < m; k++) {
        sumrow += mat[i][k];
        if (sumrow > 1)
           return false
    }
  
    // checking in column calculating sumcol
    // will be moving  row wise
    int sumcol = 0;
    for (int k = 0; k < n; k++) {
        sumcol += mat[k][j];
        if (sumcol > 1)
            return false
    }
  
    return true;
}
  
int countUnique(int mat[][MAX], int n, int m)
{
    int uniquecount = 0;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            if (mat[i][j] && 
             isUnique(mat, i, j, n, m))
                    uniquecount++;
    return uniquecount;
}
  
// Driver code
int main()
{
    int mat[][MAX] = {{0, 1, 0, 0},
                   {0, 0, 1, 0},
                   {1, 0, 0, 1}};
    cout << countUnique(mat, 3, 4);
    return 0;
}

Java

// Efficient Java program to count unique 
// cells in a binary matrix 
  
class GFG {
  
    static final int MAX = 100;
  
  // Returns true if mat[i][j] is unique 
static boolean isUnique(int mat[][], int i, int j,  
                              int n, int m) 
    // checking in row calculating sumrow 
    // will be moving  column wise 
    int sumrow = 0
    for (int k = 0; k < m; k++) { 
        sumrow += mat[i][k]; 
        if (sumrow > 1
           return false;  
    
    
    // checking in column calculating sumcol 
    // will be moving  row wise 
    int sumcol = 0
    for (int k = 0; k < n; k++) { 
        sumcol += mat[k][j]; 
        if (sumcol > 1
            return false;  
    
    
    return true
    
static int countUnique(int mat[][], int n, int m) 
    int uniquecount = 0
    for (int i = 0; i < n; i++)  
        for (int j = 0; j < m; j++)  
            if (mat[i][j]!=0 &&  
             isUnique(mat, i, j, n, m)) 
                    uniquecount++; 
    return uniquecount; 
}
// Driver code 
    static public void main(String[] args) {
        int mat[][] = {{0, 1, 0, 0},
        {0, 0, 1, 0},
        {1, 0, 0, 1}};
        System.out.print(countUnique(mat, 3, 4));
    }
}
  
// This code is contributed by Rajput-Ji

C#

      
// Efficient C# program to count unique 
// cells in a binary matrix 
using System; 
public class GFG {
   
    static readonly int MAX = 100;
  
      // Returns true if mat[i][j] is unique 
    static bool isUnique(int [,]mat, int i, int j,  
                                  int n, int m) 
    
        // checking in row calculating sumrow 
        // will be moving  column wise 
        int sumrow = 0; 
        for (int k = 0; k < m; k++) { 
            sumrow += mat[i,k]; 
            if (sumrow > 1) 
               return false;  
        
  
        // checking in column calculating sumcol 
        // will be moving  row wise 
        int sumcol = 0; 
        for (int k = 0; k < n; k++) { 
            sumcol += mat[k,j]; 
            if (sumcol > 1) 
                return false;  
        
  
        return true
    
  
    static int countUnique(int [,]mat, int n, int m) 
    
        int uniquecount = 0; 
        for (int i = 0; i < n; i++)  
            for (int j = 0; j < m; j++)  
                if (mat[i,j]!=0 &&  
                 isUnique(mat, i, j, n, m)) 
                        uniquecount++; 
        return uniquecount; 
    }
    // Driver code 
    static public void Main() {
        int [,]mat = {{0, 1, 0, 0},
        {0, 0, 1, 0},
        {1, 0, 0, 1}};
        Console.Write(countUnique(mat, 3, 4));
    }
}
   
// This code is contributed by Rajput-Ji

PHP

<?php
// PHP program to count 
// unique cells in a matrix
$MAX = 100;
  
// Returns true if 
// mat[i][j] is unique
function isUnique($mat, $i
                  $j, $n, $m)
{
    global $MAX;
      
    // checking in row calculating 
    // sumrow will be moving column wise
    $sumrow = 0;
    for ($k = 0; $k < $m; $k++)
    {
        $sumrow += $mat[$i][$k];
        if ($sumrow > 1)
        return false; 
    }
  
    // checking in column 
    // calculating sumcol 
    // will be moving row wise
    $sumcol = 0;
    for ($k = 0; $k < $n; $k++) 
    {
        $sumcol += $mat[$k][$j];
        if ($sumcol > 1)
            return false; 
    }
  
    return true;
}
  
function countUnique($mat, $n, $m)
{
    $uniquecount = 0;
    for ($i = 0; $i < $n; $i++) 
        for ($j = 0; $j < $m; $j++) 
            if ($mat[$i][$j] && 
            isUnique($mat, $i
                     $j, $n, $m))
                    $uniquecount++;
    return $uniquecount;
}
  
// Driver code
$mat = array(array(0, 1, 0, 0),
             array(0, 0, 1, 0),
             array(1, 0, 0, 1));
echo countUnique($mat, 3, 4);
  
// This code is contributed by ajit
?>


Output:

2

Time Complexity: O((n*m)*(n+m))
This goes to order of cubic due to check condition for every corresponding row and column

Method 2- O(n*m) Approach
In this approach, we are going to use extra space for rowsum array and colsum array and then check for each cell with value 1 whether the corresponding rowsum array and colsum array values are 1.

C++

// Efficient C++ program to count unique
// cells in a binary matrix
#include <bits/stdc++.h>
using namespace std;
  
const int MAX = 100;
  
int countUnique(int mat[][MAX], int n, int m)
{
    int rowsum[n], colsum[m];
    memset(colsum, 0, sizeof(colsum));
    memset(colsum, 0, sizeof(colsum));
  
    // Count number of 1s in each row
    // and in each column
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            if (mat[i][j]) {
                rowsum[i]++;
                colsum[j]++;
            }
  
    // Using above count arrays, find
    // cells
    int uniquecount = 0;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            if (mat[i][j] && 
                rowsum[i] > 1 &&
                colsum[j] > 1)
                    uniquecount++;
    return uniquecount;
}
  
// Driver code
int main()
{
    int mat[][MAX] = {{0, 1, 0, 0},
                   {0, 0, 1, 0},
                   {1, 0, 0, 1}};
    cout << countUnique(mat, 3, 4);
    return 0;
}


Output:

3

Time Complexity – O(n*m)
Auxiliary Space – O(n+m)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter