Check if the rows of a binary matrix can be made unique by removing a single column
Given a binary matrix mat[][] of size M * N. The task is to check whether the row of the matrix will be unique after deleting a column from the matrix.
Example:
Input: mat[][] = {
{1 0 1},
{0 0 0},
{1 0 0}
}
Output: Yes
After deleting 2nd column each row of matrix become unique.Input:mat[][] = {
{1 0},
{1 0}
}
Output: No
Approach:
- Take matrix as an array of string and each row consider as single string.
- Initialise a variable count = 0 to count duplicate rows in matrix.
- Now take two nested loop outer loop from i = 0 to str.length() and inner loop from j = 0 to i and for each index check if str[i] == str[j] then increment count by 1 and break the loop.
- Now check if count>= 1 then print No else print Yes.
Below is implementation of Above Approach:
C++
// C++ program to check whether the // Rows of Binary Matrix become unique // After Deleting a column. #include <bits/stdc++.h> using namespace std; // Function to check whether rows of // Binary matrix become unique after // Deleting a column of from matrix. int uniqueRows(string s[], int m, int n) { // Initialize variable count that // stores the count of duplicate rows. int i, j, count = 0; // Take two nested loop and // check whether rows already // get seen then increment // count by 1 then break the loop. for (i = 0; i < n; i++) { for (j = 0; j < i; j++) { if (s[i] == s[j]) { count++; break ; } } } // Check if count>=1 then print No // Else print Yes. if (count >= 1) { cout << "No" << endl; } else { cout << "Yes" << endl; } return 0; } // Driver code. int main() { int m = 3, n = 3; string s[] = { { 1, 0, 1 }, { 0, 0, 0 }, { 1, 0, 0 } }; // Function calling uniqueRows(s, m, n); return 0; } |
Java
// Java program to check whether the // Rows of Binary Matrix become unique // After Deleting a column. class GFG { // Function to check whether rows of // Binary matrix become unique after // Deleting a column of from matrix. static int uniqueRows( int [][]s, int m, int n) { // Initialize variable count that // stores the count of duplicate rows. int i, j, count = 0 ; // Take two nested loop and // check whether rows already // get seen then increment // count by 1 then break the loop. for (i = 0 ; i < n; i++) { for (j = 0 ; j < i; j++) { if (s[i] == s[j]) { count++; break ; } } } // Check if count>=1 then print No // Else print Yes. if (count >= 1 ) System.out.println( "No" ); else System.out.println( "Yes" ); return 0 ; } // Driver code. public static void main(String[] args) { int m = 3 , n = 3 ; int s[][] = { { 1 , 0 , 1 }, { 0 , 0 , 0 }, { 1 , 0 , 0 } }; // Function calling uniqueRows(s, m, n); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to check whether the # Rows of Binary Matrix become unique # After Deleting a column. # Function to check whether rows of # Binary matrix become unique after # Deleting a column of from matrix. def uniqueRows(s, m, n): # Initialize variable count that # stores the count of duplicate rows. i, j, count = 0 , 0 , 0 # Take two nested loop and # check whether rows already # get seen then increment # count by 1 then break the loop. for i in range (n): for j in range (i): if (s[i] = = s[j]): count + = 1 break # Check if count>=1 then print No # Else print Yes. if (count > = 1 ): print ( "No" ) else : print ( "Yes" ) # Driver code. m = 3 n = 3 s = [[ 1 , 0 , 1 ], [ 0 , 0 , 0 ], [ 1 , 0 , 0 ]] uniqueRows(s, m, n) # This code is contributed by Mohit Kumar |
C#
// C# program to check whether the // Rows of Binary Matrix become unique // After Deleting a column. using System; class GFG { // Function to check whether rows of // Binary matrix become unique after // Deleting a column of from matrix. static int uniqueRows( string []s, int m, int n) { // Initialize variable count that // stores the count of duplicate rows. int i, j, count = 0; // Take two nested loop and // check whether rows already // get seen then increment // count by 1 then break the loop. for (i = 0; i < n; i++) { for (j = 0; j < i; j++) { if (s[i] == s[j]) { count++; break ; } } } // Check if count>=1 then print No // Else print Yes. if (count >= 1) Console.WriteLine( "No" ); else Console.WriteLine( "Yes" ); return 0; } // Driver code. public static void Main(String[] args) { int m = 3, n = 3; string []s = { "101" , "000" , "100" }; // Function calling uniqueRows(s, m, n); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to check whether the // Rows of Binary Matrix become unique // After Deleting a column. // Function to check whether rows of // Binary matrix become unique after // Deleting a column of from matrix. function uniqueRows(s, m, n) { // Initialize variable count that // stores the count of duplicate rows. var i, j, count = 0; // Take two nested loop and // check whether rows already // get seen then increment // count by 1 then break the loop. for (i = 0; i < n; i++) { for (j = 0; j < i; j++) { if (s[i] == s[j]) { count++; break ; } } } // Check if count>=1 then print No // Else print Yes. if (count >= 1) { document.write( "No" ); } else { document.write( "Yes" ); } } // Driver code. var m = 3, n = 3; var s = [ [ 1, 0, 1 ], [ 0, 0, 0 ], [ 1, 0, 0 ] ]; // Function calling uniqueRows(s, m, n); // This code is contributed by importantly </script> |
Output:
Yes
Time Complexity : O(n2) ,where n is number of rows of given matrix.
Space Complexity : O(1) ,as we are not using any extra space.