package DataStructures.HashMap.Hashing;

/*

* this is algo which implies common mathematical set theory concept

* called intersection in which result is common values of both the sets

* here metaphor of sets is HashMap

Test Case:

Scanner scn=new Scanner(System.in);

int len =scn.nextInt();

int arr[]=new int[len];

int arr2[]=new int[len];

for(int i=0;i<2*len;i++) {

if(i<len)

arr[i]=scn.nextInt();

if(i>=len) {

arr2[i-len]=scn.nextInt();

}

}

System.out.println(Main(arr,arr2));

*/

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

import java.util.Set;

public class Intersection {

public static ArrayList Main(int arr[],int arr2[]) {

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

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

for(int i=0;i<arr.length;i++) {

if(hmap.containsKey(arr[i])) {

int val=hmap.get(arr[i]);

hmap.put(arr[i],val+1);

}else

hmap.put(arr[i],1);

}

ArrayList<Integer> res=new ArrayList<>();

for(int i=0;i<arr2.length;i++) {

if(hmap.containsKey(arr2[i])&&hmap.get(arr2[i])>0) {

int val=hmap.get(arr2[i]);

hmap.put(arr2[i],val-1);

res.add(arr2[i]);

}

}

return res;

}

public Intersection() {

}

}