Given a matrix of size n × m consisting of 0’s and 1’s. We need to find the number of unique cells with value 1 such that the corresponding entire row and the entire column do 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 the corresponding rows and columns of each cell with the value 1.
Implementation:
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 uniquebool 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 codeint 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 import java.io.*;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 |
Python3
# Python3 program to count unique cells in# a matrixMAX = 100# Returns true if mat[i][j] is uniquedef isUnique(mat, i, j, n, m): # checking in row calculating sumrow # will be moving column wise sumrow = 0 for k in range(m): sumrow += mat[i][k] if (sumrow > 1): return False # checking in column calculating sumcol # will be moving row wise sumcol = 0 for k in range(n): sumcol += mat[k][j] if (sumcol > 1): return False return Truedef countUnique(mat, n, m): uniquecount = 0 for i in range(n): for j in range(m): if (mat[i][j] and isUnique(mat, i, j, n, m)): uniquecount += 1 return uniquecount# Driver codemat = [[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1]]print(countUnique(mat, 3, 4))# This code is contributed by mohit kumar 29 |
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 uniquefunction 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?> |
Javascript
<script>// Efficient Javascript program to count// unique cells in a binary matrix let MAX = 100;// Returns true if mat[i][j] is unique function isUnique(mat, i, j, n, m) { // Checking in row calculating sumrow // will be moving column wise let sumrow = 0; for(let k = 0; k < m; k++) { sumrow += mat[i][k]; if (sumrow > 1) return false; } // Checking in column calculating sumcol // will be moving row wise let sumcol = 0; for(let k = 0; k < n; k++) { sumcol += mat[k][j]; if (sumcol > 1) return false; } return true; } function countUnique(mat, n, m) { let uniquecount = 0; for(let i = 0; i < n; i++) for(let j = 0; j < m; j++) if (mat[i][j] != 0 && isUnique(mat, i, j, n, m)) uniquecount++; return uniquecount; }// Driver codelet mat = [ [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 1, 0, 0, 1 ] ]; document.write(countUnique(mat, 3, 4));// This code is contributed by decode2207</script> |
Output
2
Time Complexity: O((n*m)*(n+m))
Auxiliary Space: O(1), since no extra space has been taken.
This goes to the 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.
Implementation:
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(rowsum, 0, sizeof(rowsum)); // 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 codeint 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 matriximport java.util.*;class GFG{static int MAX = 100;static int countUnique(int mat[][], int n, int m){ int []rowsum = new int[n]; int []colsum = new int[m]; // 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] != 0) { 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] != 0 && rowsum[i] == 1 && colsum[j] == 1) uniquecount++; return uniquecount;}// Driver codepublic static 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 |
Python3
# Efficient Python3 program to count unique # cells in a binary matrix MAX = 100; def countUnique(mat, n, m): rowsum = [0] * n; colsum = [0] * m; # Count number of 1s in each row # and in each column for i in range(n): for j in range(m): if (mat[i][j] != 0): rowsum[i] += 1; colsum[j] += 1; # Using above count arrays, # find cells uniquecount = 0; for i in range(n): for j in range(m): if (mat[i][j] != 0 and rowsum[i] == 1 and colsum[j] == 1): uniquecount += 1; return uniquecount; # Driver code if __name__ == '__main__': mat = [[ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 1, 0, 0, 1 ]]; print(countUnique(mat, 3, 4)); # This code is contributed by 29AjayKumar |
C#
// Efficient C# program to count unique// cells in a binary matrixusing System;class GFG{static int MAX = 100;static int countUnique(int [,]mat, int n, int m){ int []rowsum = new int[n]; int []colsum = new int[m]; // 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] != 0) { 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] != 0 && rowsum[i] == 1 && colsum[j] == 1) uniquecount++; return uniquecount;}// Driver codepublic static void Main(String[] args){ 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 |
Javascript
<script> // Efficient Javascript program to count unique cells in a binary matrix let MAX = 100; function countUnique(mat, n, m) { let rowsum = new Array(n); rowsum.fill(0); let colsum = new Array(m); colsum.fill(0); // Count number of 1s in each row // and in each column for (let i = 0; i < n; i++) for (let j = 0; j < m; j++) if (mat[i][j] != 0) { rowsum[i]++; colsum[j]++; } // Using above count arrays, find // cells let uniquecount = 0; for (let i = 0; i < n; i++) for (let j = 0; j < m; j++) if (mat[i][j] != 0 && rowsum[i] == 1 && colsum[j] == 1) uniquecount++; return uniquecount; } let mat = [[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1]]; document.write(countUnique(mat, 3, 4));</script> |
Output
2
Time Complexity : O(n*m)
Auxiliary Space: O(n+m)
This article is contributed by Rahul Chawla. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
