Given a 2D matrix arr of size N*M containing lowercase English letters, the task is to find the number of unique rows in the given matrix.
Examples:
Input: arr[][]= { {‘a’, ‘b’, ‘c’, ‘d’},
{‘a’, ‘e’, ‘f’, ‘r’},
{‘a’, ‘b’, ‘c’, ‘d’},
{‘z’, ‘c’, ‘e’, ‘f’} }
Output: 2
Explanation: The 2nd and the 4th row are unique.Input: arr[][]={{‘a’, ‘c’},
{‘b’, ‘d’},
{‘e’, ‘f’}}
Output: 3
Naive Approach: Traverse all rows one by one and for each row check if it is unique or not by comparing it with all the other rows.
Step-by-step algorithm for implementing the approach
1) Firstly, start the program and include necessary header files.
2) Define a function isUniqueRow() that takes a 2D character vector arr and an integer row as input parameters, and returns a boolean value. Now follow the below steps:
- For i from 0 to row-1 do the following:
a. Set flag to true
b. For j from 0 to the number of columns in arr[0] do the following:
b.a. If arr[i][j] is not equal to arr[row][j], set flag to false and break the loop
c. If flag is true, return false - Return true
3) Now, define another function countUniqueRows() that takes a 2D character vector arr as input parameter and returns an integer value.
- Initialize count to 0
- For i from 0 to the number of rows in arr do the following:
a. If isUniqueRow(arr, i) is true, increment count - Return count
4) Now wecall the isUniqueRow() function for each row of arr and increment the count variable if the returned value is true, and also return the final value of count after completing the loop.
5) Call the countUniqueRows() function with the test data arr and output the result to the console.
6) End the program.
C++
#include <bits/stdc++.h> using namespace std; // Function to check if the given row is unique or not bool isUniqueRow(vector<vector< char >> arr, int row) { for ( int i=0; i<row; i++) { bool flag = true ; for ( int j=0; j<arr[0].size(); j++) { if (arr[i][j] != arr[row][j]) { flag = false ; break ; } } if (flag) return false ; } return true ; } // Function to find the number of unique rows in the given matrix int countUniqueRows(vector<vector< char >> arr) { int count = 0; for ( int i=0; i<arr.size(); i++) { if (isUniqueRow(arr, i)) count++; } return count; } // Driver code int main() { vector<vector< char >> arr = { { 'a' , 'b' , 'c' , 'd' }, { 'a' , 'e' , 'f' , 'r' }, { 'a' , 'b' , 'c' , 'd' }, { 'z' , 'c' , 'e' , 'f' }, }; cout << "Number of unique rows: " << countUniqueRows(arr) << endl; return 0; } |
Python3
def isUniqueRow(arr, row): """ Function to check if the given row is unique or not. """ for i in range (row): if arr[i] = = arr[row]: return False return True def countUniqueRows(arr): """ Function to find the number of unique rows in the given matrix. """ count = 0 for i in range ( len (arr)): if isUniqueRow(arr, i): count + = 1 return count # Driver code if __name__ = = "__main__" : arr = [ [ 'a' , 'b' , 'c' , 'd' ], [ 'a' , 'e' , 'f' , 'r' ], [ 'a' , 'b' , 'c' , 'd' ], [ 'z' , 'c' , 'e' , 'f' ], ] print ( "Number of unique rows: " , countUniqueRows(arr)) |
Javascript
// Function to check if the given row is unique or not function isUniqueRow(arr, row) { for (let i = 0; i < row; i++) { let flag = true ; for (let j = 0; j < arr[0].length; j++) { if (arr[i][j] !== arr[row][j]) { flag = false ; break ; } } if (flag) { return false ; } } return true ; } // Function to find the number of unique rows in the given matrix function countUniqueRows(arr) { let count = 0; for (let i = 0; i < arr.length; i++) { if (isUniqueRow(arr, i)) { count++; } } return count; } // Driver code const arr = [ [ 'a' , 'b' , 'c' , 'd' ], [ 'a' , 'e' , 'f' , 'r' ], [ 'a' , 'b' , 'c' , 'd' ], [ 'z' , 'c' , 'e' , 'f' ], ]; console.log( 'Number of unique rows: ' + countUniqueRows(arr)); |
Java
import java.util.Arrays; class UniqueRows { // Function to check if the given row is unique or not static boolean isUniqueRow( char [][] arr, int row) { for ( int i = 0 ; i < row; i++) { if (Arrays.equals(arr[i], arr[row])) { return false ; } } return true ; } // Function to find the number of unique rows in the // given matrix static int countUniqueRows( char [][] arr) { int count = 0 ; for ( int i = 0 ; i < arr.length; i++) { if (isUniqueRow(arr, i)) { count++; } } return count; } // Driver code public static void main(String[] args) { char [][] arr = { { 'a' , 'b' , 'c' , 'd' }, { 'a' , 'e' , 'f' , 'r' }, { 'a' , 'b' , 'c' , 'd' }, { 'z' , 'c' , 'e' , 'f' } }; System.out.println( "Number of unique rows: " + countUniqueRows(arr)); } } |
C#
using System; using System.Collections.Generic; public class Gfg { // Function to check if the given row is unique or not public static bool isUniqueRow(List<List< char >> arr, int row) { for ( int i = 0; i < row; i++) { bool flag = true ; for ( int j = 0; j < arr[0].Count; j++) { if (arr[i][j] != arr[row][j]) { flag = false ; break ; } } if (flag) return false ; } return true ; } // Function to find the number of unique rows in the given matrix public static int countUniqueRows(List<List< char >> arr) { int count = 0; for ( int i = 0; i < arr.Count; i++) { if (isUniqueRow(arr, i)) count++; } return count; } // Driver code public static void Main() { List<List< char >> arr = new List<List< char >> { new List< char >{ 'a' , 'b' , 'c' , 'd' }, new List< char >{ 'a' , 'e' , 'f' , 'r' }, new List< char >{ 'a' , 'b' , 'c' , 'd' }, new List< char >{ 'z' , 'c' , 'e' , 'f' } }; Console.WriteLine( "Number of unique rows: " + countUniqueRows(arr)); } } |
Number of unique rows: 3
Time complexity: O(N2 X M) where n is the number of rows and m is the number of columns in the input matrix. This is because the isUniqueRow function has a nested loop that compares each row with every other row before it.
Auxiliary Space: O(1) This is because the isUniqueRow() function uses constant space for its local variables and The countUniqueRows() function uses an integer variable count and calls the isUniqueRow() function, so its space complexity depends on the space complexity of isUniqueRow().
Efficient Approach: Using Hashing, we can store the key as a string containing all the characters in that row and its frequency as the value. And traverse all the rows in the map and if its frequency is 1 then count it as unique.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to find number of unique rows int uniqueRows(vector<vector< char > > arr) { // Map to store the frequency of // each row as string unordered_map<string, int > mp; string t; for ( auto x : arr) { t = "" ; for ( auto y : x) { t += y; } mp[t] += 1; } int cnt = 0; // Counting unique rows for ( auto x : mp) { if (x.second == 1) { cnt += 1; } } return cnt; } // Driver Code int main() { vector<vector< char > > arr = { { 'a' , 'b' , 'c' , 'd' }, { 'a' , 'e' , 'f' , 'r' }, { 'a' , 'b' , 'c' , 'd' }, { 'z' , 'c' , 'e' , 'f' }, }; cout << uniqueRows(arr); return 0; } |
Java
// Java code to implement the above approach import java.util.*; class GFG{ // Function to find number of unique rows static int uniqueRows( char [][] arr) { // Map to store the frequency of // each row as String HashMap<String, Integer> mp = new HashMap<>(); String t= "" ; for ( char []x : arr) { t = "" ; for ( char y : x) { t += y; } if (mp.containsKey(t)) { mp.put(t, mp.get(t)+ 1 ); } else mp.put(t, 1 ); } int cnt = 0 ; // Counting unique rows for (Map.Entry<String,Integer> x : mp.entrySet()) { if (x.getValue() == 1 ) { cnt += 1 ; } } return cnt; } // Driver Code public static void main(String[] args) { char [][] arr = { { 'a' , 'b' , 'c' , 'd' }, { 'a' , 'e' , 'f' , 'r' }, { 'a' , 'b' , 'c' , 'd' }, { 'z' , 'c' , 'e' , 'f' }, }; System.out.print(uniqueRows(arr)); } } // This code is contributed by Rajput-Ji |
Python3
# Python 3 code to implement the above approach from collections import defaultdict # Function to find number of unique rows def uniqueRows(arr): # Map to store the frequency of # each row as string mp = defaultdict( int ) t = "" for x in arr: t = "" for y in x: t + = y mp[t] + = 1 cnt = 0 # Counting unique rows for x in mp: if (mp[x] = = 1 ): cnt + = 1 return cnt # Driver Code if __name__ = = "__main__" : arr = [ [ 'a' , 'b' , 'c' , 'd' ], [ 'a' , 'e' , 'f' , 'r' ], [ 'a' , 'b' , 'c' , 'd' ], [ 'z' , 'c' , 'e' , 'f' ], ] print (uniqueRows(arr)) # This code is contributed by ukasp. |
C#
// C# code to implement the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function to find number of unique rows static int uniqueRows( char [,]arr) { // Map to store the frequency of // each row as string Dictionary< string , int > mp = new Dictionary< string , int >(); string t; for ( int i = 0; i < arr.GetLength(0); i++) { t = "" ; for ( int j = 0; j < arr.GetLength(1); j++) { t += arr[i, j]; } if (mp.ContainsKey(t)) { mp[t] = mp[t] + 1; } else { mp.Add(t, 1); } } int cnt = 0; // Counting unique rows foreach ( var x in mp.Keys) { if (mp[x] == 1) { cnt += 1; } } return cnt; } // Driver Code public static void Main() { char [,]arr = { { 'a' , 'b' , 'c' , 'd' }, { 'a' , 'e' , 'f' , 'r' }, { 'a' , 'b' , 'c' , 'd' }, { 'z' , 'c' , 'e' , 'f' }, }; Console.Write(uniqueRows(arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find number of unique rows function uniqueRows(arr) { // Map to store the frequency of // each row as string let mp = new Map(); let t; for (let x of arr) { t = "" ; for (let y of x) { t += y; } if (!mp.has(t)) mp.set(t, 1); else mp.set(t, mp.get(t) + 1); } let cnt = 0; // Counting unique rows for (let [key, val] of mp) { if (val == 1) { cnt += 1; } } return cnt; } // Driver Code let arr = [ [ 'a' , 'b' , 'c' , 'd' ], [ 'a' , 'e' , 'f' , 'r' ], [ 'a' , 'b' , 'c' , 'd' ], [ 'z' , 'c' , 'e' , 'f' ], ]; document.write(uniqueRows(arr)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N*M), Where N is the number of rows and M is the number of columns in the matrix
Auxiliary Space: O(N*M), Where N is the number of rows and M is the number of columns in the matrix
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!