Check if two unsorted arrays (with duplicates allowed) have same elements
Given two unsorted arrays, check whether both arrays have the same set of elements or not.
Examples:
Input : A = {2, 5, 6, 8, 10, 2, 2} B = {2, 5, 5, 6, 8, 5, 6} Output : No Input : A = {2, 5, 6, 8, 2, 10, 2} B = {2, 5, 6, 8, 2, 10, 2} Output : Yes Input : A = {2, 5, 8, 6, 10, 2, 2} B = {2, 5, 6, 8, 2, 10, 2} Output : Yes
Method 1 (Simple):
A simple solution to this problem is to check if each element of A is present in B. But this approach will lead to a wrong answer in case of multiple instances of an element is present in B. To overcome this issue, we mark visited instances of B[] using an auxiliary array visited[].
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to check if both arrays are same bool areSameSet(vector< int > A, vector< int > B) { int n = A.size(); if (B.size() != n) return false ; // visited array is used to handle duplicates vector< bool > visited(n, false ); // each element of A is matched // against each element of B for ( int i = 0; i < n; i++) { int j = 0; for (j = 0; j < n; j++) { if (A[i] == B[j] && visited[j] == false ) { visited[j] = true ; break ; } } // If we could not find A[i] in B[] if (j == n) return false ; } return true ; } // Driver code int main() { vector< int > A, B; A.push_back(2); A.push_back(5); A.push_back(10); A.push_back(6); A.push_back(8); A.push_back(2); A.push_back(2); B.push_back(2); B.push_back(5); B.push_back(6); B.push_back(8); B.push_back(10); B.push_back(2); B.push_back(2); areSameSet(A, B)? cout << "Yes" : cout << "No" ; } |
Java
// Java implementation of the above approach import java.util.*; class GFG { // Function to check if both arrays are same static boolean areSameSet(Vector<Integer> A, Vector<Integer> B) { int n = A.size(); if (B.size() != n) { return false ; } // visited array is used to handle duplicates Vector<Boolean> visited = new Vector<Boolean>(); for ( int i = 0 ; i < n; i++) { visited.add(i, Boolean.FALSE); } // each element of A is matched // against each element of B for ( int i = 0 ; i < n; i++) { int j = 0 ; for (j = 0 ; j < n; j++) { if (A.get(i) == B.get(j) && visited.get(j) == false ) { visited.add(j, Boolean.TRUE); break ; } } // If we could not find A[i] in B[] if (j == n) { return false ; } } return true ; } // Driver code public static void main(String[] args) { Vector<Integer> A = new Vector<>(); Vector<Integer> B = new Vector<>(); A.add( 2 ); A.add( 5 ); A.add( 10 ); A.add( 6 ); A.add( 8 ); A.add( 2 ); A.add( 2 ); B.add( 2 ); B.add( 5 ); B.add( 6 ); B.add( 8 ); B.add( 10 ); B.add( 2 ); B.add( 2 ); if (areSameSet(A, B)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } /* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the above approach # Function to check if both arrays are same def areSameSet(A, B): n = len (A) if ( len (B) ! = n): return False # visited array is used to handle duplicates visited = [ False for i in range (n)] # each element of A is matched # against each element of B for i in range (n): j = 0 for j in range (n): if (A[i] = = B[j] and visited[j] = = False ): visited[j] = True break # If we could not find A[i] in B[] if (j = = n): return False return True # Driver code A = [] B = [] A.append( 2 ) A.append( 5 ) A.append( 10 ) A.append( 6 ) A.append( 8 ) A.append( 2 ) A.append( 2 ) B.append( 2 ) B.append( 5 ) B.append( 6 ) B.append( 8 ) B.append( 10 ) B.append( 2 ) B.append( 2 ) if (areSameSet(A, B)): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by mohit kumar |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG { // Function to check if both arrays are same static Boolean areSameSet(List< int > A, List< int > B) { int n = A.Count; if (B.Count != n) { return false ; } // visited array is used to handle duplicates List<Boolean> visited = new List<Boolean>(); for ( int i = 0; i < n; i++) { visited.Insert(i, false ); } // each element of A is matched // against each element of B for ( int i = 0; i < n; i++) { int j = 0; for (j = 0; j < n; j++) { if (A[i] == B[j] && visited[j] == false ) { visited.Insert(j, true ); break ; } } // If we could not find A[i] in B[] if (j == n) { return false ; } } return true ; } // Driver code public static void Main(String[] args) { List< int > A = new List< int >(); List< int > B = new List< int >(); A.Add(2); A.Add(5); A.Add(10); A.Add(6); A.Add(8); A.Add(2); A.Add(2); B.Add(2); B.Add(5); B.Add(6); B.Add(8); B.Add(10); B.Add(2); B.Add(2); if (areSameSet(A, B)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the above approach // Function to check if both arrays are same function areSameSet(A,B) { let n = A.length; if (B.length != n) { return false ; } // visited array is used to handle duplicates let visited = []; for (let i = 0; i < n; i++) { visited.push( false ); } // each element of A is matched // against each element of B for (let i = 0; i < n; i++) { let j = 0; for (j = 0; j < n; j++) { if (A[i] == B[j] && visited[j] == false ) { visited[j]= true ; break ; } } // If we could not find A[i] in B[] if (j == n) { return false ; } } return true ; } // Driver code let A=[]; let B=[]; A.push(2); A.push(5); A.push(10); A.push(6); A.push(8); A.push(2); A.push(2); B.push(2); B.push(5); B.push(6); B.push(8); B.push(10); B.push(2); B.push(2); if (areSameSet(A, B)) { document.write( "Yes" ); } else { document.write( "No" ); } // This code is contributed by patel2127 </script> |
Output:
Yes
Time complexity: O(n^2).
Method 2 (Sorting):
Sort both the arrays and compare corresponding elements of each array.
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to check if both arrays are same bool areSameSet(vector< int > A, vector< int > B) { int n = A.size(); if (B.size() != n) return false ; sort(A.begin(), A.end()); sort(B.begin(), B.end()); // Compare corresponding elements for ( int i = 0; i < n; i++) if (A[i] != B[i]) return false ; return true ; } int main() { vector< int > A, B; A.push_back(2); A.push_back(5); A.push_back(10); A.push_back(6); A.push_back(8); A.push_back(2); A.push_back(2); B.push_back(2); B.push_back(5); B.push_back(6); B.push_back(8); B.push_back(10); B.push_back(2); B.push_back(2); areSameSet(A, B)? cout << "Yes" : cout << "No" ; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to check if both arrays are same static boolean areSameSet(Vector<Integer> A, Vector<Integer> B) { int n = A.size(); if (B.size() != n) { return false ; } Collections.sort(A); Collections.sort(B); // Compare corresponding elements for ( int i = 0 ; i < n; i++) { if (A.get(i) != B.get(i)) { return false ; } } return true ; } // Driver code public static void main(String[] args) { Vector<Integer> A = new Vector<>(); Vector<Integer> B = new Vector<>(); A.add( 2 ); A.add( 5 ); A.add( 10 ); A.add( 6 ); A.add( 8 ); A.add( 2 ); A.add( 2 ); B.add( 2 ); B.add( 5 ); B.add( 6 ); B.add( 8 ); B.add( 10 ); B.add( 2 ); B.add( 2 ); if (areSameSet(A, B)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to check if # both arrays are same def areSameSet(A, B): n = len (A) if ( len (B) ! = n): return False A.sort() B.sort() # Compare corresponding # elements for i in range (n): if (A[i] ! = B[i]): return False return True # Driver code if __name__ = = "__main__" : A = [] B = [] A.append( 2 ) A.append( 5 ) A.append( 10 ) A.append( 6 ) A.append( 8 ) A.append( 2 ) A.append( 2 ) B.append( 2 ) B.append( 5 ) B.append( 6 ) B.append( 8 ) B.append( 10 ) B.append( 2 ) B.append( 2 ) if areSameSet(A, B): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Chitranayal |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to check if both arrays are same static Boolean areSameSet(List< int > A, List< int > B) { int n = A.Count; if (B.Count!= n) { return false ; } A.Sort(); B.Sort(); // Compare corresponding elements for ( int i = 0; i < n; i++) { if (A[i] != B[i]) { return false ; } } return true ; } // Driver code public static void Main(String[] args) { List< int > A = new List< int >(); List< int > B = new List< int >(); A.Add(2); A.Add(5); A.Add(10); A.Add(6); A.Add(8); A.Add(2); A.Add(2); B.Add(2); B.Add(5); B.Add(6); B.Add(8); B.Add(10); B.Add(2); B.Add(2); if (areSameSet(A, B)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation of the approach // Function to check if both arrays are same function areSameSet(A, B) { let n = A.length; if (B.length != n) { return false ; } A.sort( function (a, b){ return a - b;}); B.sort( function (a, b){ return a - b;}); // Compare corresponding elements for (let i = 0; i < n; i++) { if (A[i] != B[i]) { return false ; } } return true ; } // Driver code let A = []; let B = []; A.push(2); A.push(5); A.push(10); A.push(6); A.push(8); A.push(2); A.push(2); B.push(2); B.push(5); B.push(6); B.push(8); B.push(10); B.push(2); B.push(2); if (areSameSet(A, B)) { document.write( "Yes" ); } else { document.write( "No" ); } // This code is contributed by unknown2108 </script> |
Output:
Yes
Time Complexity: O(n*log(n)).
Method 3 (Hashing):
We can decrease the time complexity of the above problem by using a Hash table. First, we iterate through A and mark the number of instances of each element of A in a Hash Table. Then we iterate through B and decrease the corresponding value in the hash table. If in the end if all the entries of the hash table are zero, the answer will be “Yes” else “No”.
C++
// C++ program to implement Naive approach // to remove duplicates #include <bits/stdc++.h> using namespace std; bool areSameSet(vector< int > A, vector< int > B){ int n = A.size(); // If the size of vector A and vector B is not equal return False if (B.size() != n) return false ; // Create a hash table to // number of instances unordered_map< int , int > m; // for each element of A // increase it's instance by 1. for ( int i = 0; i < n; i++) m[A[i]]++; // for each element of B // decrease it's instance by 1. for ( int i = 0; i < n; i++) m[B[i]]--; // Iterate through map and check if // any entry is non-zero for ( auto i : m){ if (i.second != 0){ return false ; } } return true ; } // driver code to test above function int main(){ // initializing vector A vector< int > A = {2, 5, 10, 6, 8, 2, 2}; // initializing vector B vector< int > B = {2, 5, 6, 8, 10, 2, 2}; // Function call areSameSet(A, B)? cout << "Yes" : cout << "No" ; } |
Java
// Java program to implement Naive approach // to remove duplicates import java.util.HashMap; class GFG { static boolean areSameSet( int [] A, int [] B) { int n = A.length; if (B.length != n) return false ; // Create a hash table to // number of instances HashMap<Integer, Integer> m = new HashMap<>(); // for each element of A // increase it's instance by 1. for ( int i = 0 ; i < n; i++) m.put(A[i], m.get(A[i]) == null ? 1 : m.get(A[i]) + 1 ); // for each element of B // decrease it's instance by 1. for ( int i = 0 ; i < n; i++) m.put(B[i], m.get(B[i]) - 1 ); // Iterate through map and check if // any entry is non-zero for (HashMap.Entry<Integer, Integer> entry : m.entrySet()) if (entry.getValue() != 0 ) return false ; return true ; } // Driver Code public static void main(String[] args) { int [] A = { 2 , 5 , 10 , 6 , 8 , 2 , 2 }; int [] B = { 2 , 5 , 6 , 8 , 10 , 2 , 2 }; if (areSameSet(A, B)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to implement Naive # approach to remove duplicates def areSameSet(A, B): n = len (A) if ( len (B) ! = n): return False # Create a hash table to # number of instances m = {} # For each element of A # increase it's instance by 1. for i in range (n): if A[i] not in m: m[A[i]] = 1 else : m[A[i]] + = 1 # For each element of B # decrease it's instance by 1. for i in range (n): if B[i] in m: m[B[i]] - = 1 # Iterate through map and check if # any entry is non-zero for i in m: if (m[i] ! = 0 ): return False return True # Driver Code A = [] B = [] A.append( 2 ) A.append( 5 ) A.append( 10 ) A.append( 6 ) A.append( 8 ) A.append( 2 ) A.append( 2 ) B.append( 2 ) B.append( 5 ) B.append( 6 ) B.append( 8 ) B.append( 10 ) B.append( 2 ) B.append( 2 ) if (areSameSet(A, B)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to implement Naive approach // to remove duplicates using System; using System.Collections.Generic; class GFG { static bool areSameSet( int [] A, int [] B) { int n = A.Length; if (B.Length != n) return false ; // Create a hash table to // number of instances Dictionary< int , int > m = new Dictionary< int , int >(); // for each element of A // increase it's instance by 1. for ( int i = 0; i < n; i++) if (m.ContainsKey(A[i])) m[A[i]] = m[A[i]] + 1; else m.Add(A[i], 1); // for each element of B // decrease it's instance by 1. for ( int i = 0; i < n; i++) if (m.ContainsKey(B[i])) m[B[i]] = m[B[i]] - 1; // Iterate through map and check if // any entry is non-zero foreach (KeyValuePair< int , int > entry in m) if (entry.Value != 0) return false ; return true ; } // Driver Code public static void Main(String[] args) { int [] A = { 2, 5, 10, 6, 8, 2, 2 }; int [] B = { 2, 5, 6, 8, 10, 2, 2 }; if (areSameSet(A, B)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to implement Naive approach // to remove duplicates function areSameSet(A,B) { let n = A.length; if (B.length != n) return false ; // Create a hash table to // number of instances let m = new Map(); // for each element of A // increase it's instance by 1. for (let i = 0; i < n; i++) m.set(A[i], m.get(A[i]) == null ? 1 : m.get(A[i]) + 1); // for each element of B // decrease it's instance by 1. for (let i = 0; i < n; i++) m.set(B[i], m.get(B[i]) - 1); // Iterate through map and check if // any entry is non-zero for (let [key, value] of m.entries()) if (value != 0) return false ; return true ; } // Driver Code let A=[2, 5, 10, 6, 8, 2, 2 ]; let B=[2, 5, 6, 8, 10, 2, 2]; if (areSameSet(A, B)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by rag2127 </script> |
Output:
Yes
Time Complexity: O(n), where n is the number of elements in the given vector.
Auxiliary Space: O(n)