CareerCup

1. Load the items of the array A into a HashSet S. Each insert will take amortized O(1) time.
2. Iterate through the integers of array B and check if the HashSet contains the integer. Each lookup also takes O(1) time.

So the overall algorithm is O(n) time.

Sort array A --> nlogn time
Sort array B -->nlogn time
Now binary search each element of one array to other. takes nlogn+nlogn time
Total nlogn time

CommonElement(int A[], int i, int B[], int j){
if ( i < 0 II j < 0) return;
else{
if (A[i] == B[j] ) {
common[++k] = A[i] ; // Global K =-1
CommonElement(A,i-1,B,j-1);
}
else{
CommonElement(A,i,B,j-1);
CommonElement(A,i-1,B,j-1);
}
}

solution 1
use HashSet as suggested

solution 2
sort one array and binary search every element in another array

solution 3
sort both arrays, traverse them at the same time and add the same element

public ArrayList<Integer> intersect(ArrayList<Integer> a, ArrayList<Integer> b)
	{
		ArrayList<Integer> c = new ArrayList<Integer>();
		int i = 0;
		int j = 0;
		while(i < a.size() && j < b.size()) {
			for(; i < a.size() && j < b.size() && a.get(i) < b.get(j); i++);
			for(; j < b.size() && i < a.size() && b.get(j) < a.get(i); j++);
			if(i < a.size() && j < b.size() && a.get(i) == b.get(j)) {
				c.add(a.get(i));
				i++;
				j++;
			}
		}
		return c;
	}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        IntegerFunctions iFunc = new IntegerFunctions();
        int[] Array1 = new int[] { 0, 1, 5, 7, 3, 4, 5, 6, 3, 11 };
        int[] Array2 = new int[] { 7, 23, 1, 1, 1, 7, 8, 11, 11 };
       iFunc.GetCommonItems(Array1, Array2);
    }
}

public class IntegerFunctions
{
    internal Dictionary<int, int> GetCommonItems(int[] Array1, int[] Array2)
    {
        Dictionary<int, int> retDict = new Dictionary<int, int>();
        if (Array1.Length == 0 || Array2.Length == 0) return retDict;
        int iCount = 0;
        Dictionary<int, int> iDict = new Dictionary<int, int>();
        for (int i = 0; i < Array1.Length; i++)
        {
            if (!iDict.ContainsKey(Array1[i]))
            {
                iCount++;
                iDict.Add(Array1[i], iCount);
            }

        }
        iCount = 0;
        for (int j = 0; j < Array2.Length; j++)
        {
            if (iDict.ContainsKey(Array2[j]))
            {
                if (!retDict.ContainsKey(Array2[j]))
                {
                    retDict.Add(Array2[j], iCount);
                    Console.WriteLine("Matching Element: " + Array2[j]);
                }
            }
        }

        return retDict;
    }
}

Implementation in java by using hashset.

public int common(Integer[] a, Integer[] b) {
		HashSet hashSet =new HashSet();
		for(int i = 0; i < a.length ; i++) { 
			hashSet.add(a[i]);	
		}
		for(int i = 0; i < b.length ; i++) {
			if(hashSet.contains(b[i])) {
				System.out.println("COMMON : "+b[i]);
				return b[i];
			}
		}
		return 0;

}

def commonElements(a1,a2):
	for element in a2:
		if element not in a1:
			a2.remove(element) 
	return a2