HashMap/HashSet are an alternative for unodered map in c++

Recently I came across a problem in which I needed to have linear time complexity while finding the union of two array.

It was possible to do it for sorted array , but in an unsorted array , the process of sorting itself takes o(n²) complexity :

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Arrays;

class GFG {
public static void main (String[] args) {
//code
Scanner sc = new Scanner(System.in);

int t = sc.nextInt();
while(t>0)
{
int n = sc.nextInt();
int m = sc.nextInt();

int a[] = new int[n];
int b[] = new int[m];


for(int i=0;i<n;i++)
{
a[i] = sc.nextInt();

}

for(int i=0;i<m;i++)
{
b[i] = sc.nextInt();

}
Arrays.sort(a, 0, n);
Arrays.sort(b, 0, m);

int nn= n;



// i am assuming that both the arrays are sorted
int l;


if(n<=m){
l=n;
}
else{
l=m;
}

int arr[] = new int[l];

int pa=0 , pb=0 , pl=0 , c=0;

while(pa <n &&pb <m)
{
if(a[pa]== b[pb])
{

arr[pl] = a[pa];
pl++;
pa++;
pb++;
c++;
}

else if(a[pa]<b[pb])
{
pa++;
}
else if(a[pa]>b[pb])
{
pb++;
}
}
//done with entering no. in array

System.out.println(c);

t — ;
}
}
}

so to tackle this issue(according to a solution I found online) , instead of performing sorting we can use unordered map for using the number as a key .

similarly in hashmap we can insert key value pairs to solve this problem.

Hashmap are classes that implement map interface(map interface extends collection).

import java.util.HashMap; // import the HashMap class

HashMap<Integer, Integer> union = new HashMap<Integer, Integer>();

so , we can run a loop through both the arrays and store the numbers inside them in union as as unique keys . and now to get the union of two arrays we can just get the key set of union .

but for my implementation it was observered that HashSet was more useful as their was no need of the value part in the collection.so I used hashset instead to store the unique elements of both array and the used size() to find out the count of the union of both the array.

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
//code
Scanner sc = new Scanner(System.in);

int t = sc.nextInt();
while(t>0)
{
int n = sc.nextInt();
int m = sc.nextInt();

int a[] = new int[n];
int b[] = new int[m];


for(int i=0;i<n;i++)
{
a[i] = sc.nextInt();

}

for(int i=0;i<m;i++)
{
b[i] = sc.nextInt();

}


//done with entering no. in array

HashSet<Integer> union = new HashSet<Integer>();

for(int i=0;i<n;i++)
{
int key = a[i] ;
union.add(key);
}

for(int i=0;i<m;i++)
{
int key = b[i] ;
union.add(key);

}
//all the unique nos. are present in the hashset union.
System.out.println(union.size());

t — ;
}
}
}

So this was my approach which took 2.10 sec . Thank You!