CareerCup

- Create a hashmap of <element, count> pairs from the first array.
- Iterate through the second array and find matching elements.
- If the count of the matching element is greater than 0, print the element and
decrease the count in the map by 1.

static void commonElements(int[] arr1, int[] arr2){
        HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
        for(int e : arr1){
            if(countMap.containsKey(e)){
                int count = countMap.get(e);
                countMap.put(e, count + 1);
                
            }else{
                countMap.put(e , 1);
            }
            
        }
        
        for(int e : arr2){
            if(countMap.containsKey(e)){
                int count = countMap.get(e);
                if(count > 0){
                    System.out.println(e);
                    countMap.put(e , count - 1);
                }
            }
            
        }
        
    }

I think probably the hash is one option here.

1> I will hash the elements of one array into the hash table.
2> For Every element in the second array try to find the collision and for each collision print value.
Time Complexity = O(m)
Space Complexity = Hash Table Creation.

Create a bit set and while iterating through array1, set the bit corresponding to the value at that index. Now traverse array2 and if the bit for the current index in array2 is set, then display this value.

I've found a nice answer for this question:

import java.util.*;
public class CountTest {     
    public static void main(String... args) {        
        Integer[] array1 = {9, 4, 6, 2, 10, 10};
        Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9};                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) {
            if (hashSet.contains(array2[i])) {
                commonElements.add(array2[i]);
            }
        }
        System.out.println("Common elements " + commonElements);
    }    
}

My approach.

1>Use inbuilt sort routine and sort both arrays.
2>iterate both arrays with two different pointers.
3>compare values and if equal in both array append to new blank array
4>if not equal advance pointer of array with smaller value.

total O(m+n)

1) FInd the length of the each arrays
2) Sort the Biggest size array
3) take the first element of the non-sorted array do binary search on the sorted array continue till last element of non-sorted array.

then complexity will be size of non sorted array * log(Size of sorted array)

1) FInd the length of the each arrays
2) Sort the Biggest size array
3) take the first element of the non-sorted array do binary search on the sorted array continue till last element of non-sorted array.

then complexity will be size of non sorted array * log(Size of sorted array) + sorting of bigger array

Use a third array temp:

1.Put all the elements of arr1 into temp such that 5 goes to temp[5] ...
2.Iterate over arr2 and for every value check if temp[value]==null to find duplicates

@ learner this is the exact solution expected...

Sort both array then find out common elements!!

#include<stdio.h>

int hashtable[10];
int hashcount[10];

int hashval (int key)
{
    return key;
}

void buildhash (int *a, int size)
{
    int i,hash;

    for (i = 0; i < size; i++)
    {
        hash = hashval(a[i]);
        hashcount[hash]++;
        hashtable[hash] = a[i];
    }
}

int main() {
    int i,hash;
    int a[] = {5,6,4,2,2};
    int b[] = {4,2,2,1,6,5,5,3};

    buildhash(a,sizeof(a)/sizeof(int));

    for (i = 0; i<(sizeof(b)/sizeof(int)); i++) {
        hash = hashval(b[i]);
        if (hashtable[hash] && hashcount[hash]) {
            printf("%d ",b[i]);
            hashcount[hash]--;
        }
    }
    printf("\n");
    return 0;
}

@teja : Thank you teja

I Think a better solution could be as below ( Except its not printing repetitive common elements )

import java.util.HashSet;
import java.util.Set;


public class ArrayIntersection {
static int[] arr1 = {5,6,4,2,2};
static int[] arr2={4,2,2,1};
public static void main(String[] args) {
Set<Integer> setA = new HashSet<Integer>();
Set<Integer> setB = new HashSet<Integer>();
for(Integer iFirstArray : arr1){
setA.add(iFirstArray);
}
for(Integer isecondtArray : arr2){
setB.add(isecondtArray);
}

Set<Integer> common = new HashSet<Integer>(setA);
common.retainAll(setB);
System.out.println(common);
}

}

for i in b:
	if i in a:
		andlist+=(i,)

1. Create a map of array 1 ( Key = Number, Value = 0)
2. Iterate through array 2 ( Increment value by 1 if match)

Time Complexity O(M+N)
Space Complexity O(M)

#include <iostream>
#include <map>
using namespace std;

void common(int arr1[], int arr2[], map<int, int> &data, int size1, int size2)
{
	// Arr1 = M, Arr2 = N

	// Insert Data
	// Insert O(M), Space O(M)
	for(int i=0; i<size1; i++)
	{
		pair<int, int> p(arr1[i], 0);

		if ( data.count(arr1[i]) == 0)
			data.insert(p);
		// Igonore Duplicate
	}
	
	// Search
	for(int i=0; i<size2; i++)
	{
		if ( data.count(arr2[i]) > 0)
			data.at(arr2[i]) += 1;
	}

}

int main()
{
	
	int arr1[] = {5,6,4,2,2};
	int arr2[] = {4,2,2,1};

	map<int, int> m;

	common(arr1, arr2, m, sizeof(arr1)/sizeof(arr1[0]), sizeof(arr2)/sizeof(arr2[0]));

	return 0;
}

I am using bit map to find the intersected values. But the range is limited
for integer (0-65535).

Complexity O(m+n)

#include <stdio.h>

int main() {
int arr1[] = {5,6,4,2,2};
int arr2[] = {4,2,2,10,15,12};
int hash = 0;
for (int i=0;i<5;i++) {
hash = hash | (1<<arr1[i]);
}


for (int j=0;j<6;j++) {
int hash1 = hash;
if (((hash1 >> arr2[j]) & 1) == 1) {
printf("\nIntersected value %d",arr2[j]);
}
}
}

1. Create a structure:
struct hash{
int element;
int count;
}
2. Create a hash table of above structure.
3. Traverse first array and store in hash table and increment count value if value is still present in hash table.
3. Traverse second array and decrements value of count in hash table till it is greater than 0. And print value of second array.

Hi Please find my approach :

public static void main(String args[]){
int[] arr1 = {5,6,4,2,2};
int[]arr2 = {4,2,2,1};

for(int i=0;i<arr1.length-1;i++){

for(int j=0;j<arr1.length-1;j++){

if(arr1[i]==arr2[j]){
System.out.print(arr1[i]);
}
}
}
}