CareerCup

Use hashtable. Iterate through the first array and put elements in the hashtable. Then, iterate through the second array, print out elements already in the hashtable. O(N)

to- Anonymous on November 01, 2008

I guess the complexity of your solution will be nlogn. So in my point view hash table approach is better.

Was asked this on a phone screen

There are many ways to solve this problem. They are described below :-

1. Sorting - Sort both the arrays. Now use two iterators to traverse through each element of both the arrays. Adjust the iterators after every traversal and print the common elements.
Pseudo Code :-

void intersection(int nArray1[], int nLength1, int nArray2[], int nLength2)
//
sort(nArray1, nLength1)
sort(nArray2, nLength2)

int i <- 0
int j <- 0
while i < nLength1 && j < nLength2
do
- if nArray1[i] is equal to nArray2[j]
then
- - print nArray1[i]
- - i++
- - j++
- else if nArray1[i] < nArray2[j]
- - i++
- else
- - j++

Complexity :- O(nlogn + mlogm)

2. Sort the smaller array and use binary search for each element in the larger array.
It has better complexity than the 1st method.

void intersection(int nArray1[], int nLength1, int nArray2[], int nLength2)
//
sort(nArray2, nLength2) // Imagining that second array is smaller

int i <- 0
while i < nLength1
do
- if nArray1[i] is found in nArray2 by binary search method
- then
- - print nArray1[i]
- i++

Complexity :- O(mlogm + nlogm)

3. Hashing :- Store the elements of smaller array in a hash map.
Now, traverse through each and every element of first array, if the hash map exists for that element then print that element else increment the iterator.
The pseudo code is like this :-

void intersection(int nArray1[], int nLength1, int nArray2[], int nLength2)
//

int i <- 0
while i < nLength2
do
- hMap[nArray2[i]] <- true
- i++

i <- 0
while i < nLength1
do
- if hMap[nArray1[i]] exists
- then
- - print nArray1[i]
- i++

Complexity :- O(n + m)
Space complexity :- O(m)

4. Binary Search tree :- This method is same as hashing however, this time we're storing the smaller array elements in a binary search tree and then for each element in array 1 we're finding whether it's present in the tree or not.

Complexity :- O(mlogm + nlogm)
Space complexity :- O(m)

if binary tree is made of first array and then search for the elements in the second array.

Agreed with JD, BUT then again its matter of time-space trade-off.
We do not know the range of numbers. and if the range is very large w.r.t the elements in the array, the binary tree logic works fine.
In short,
Method 1)
Prepare a hash table of Array A1 and then search for elements of Array A2 in this table.
Time - O(n)
Space - O(range) // range>>n

Method 2)
Prepare BST of A1 and search for elements of A2 in A1.
Time - O(nLgn)
Space - O(n)

Method 3)
Sort both the lists O(nlgn)
Then perform a scan of both A1 & A2 similar to Merging to find common elements. O(n)
Therefore,
Time - O(nlgn)
Space - O(n) // Assuming we apply merge sort so extra space requirement is O(n)

if memory is scarce, you can sorth both arrays, and then perform a string matching on both to get the intersection.

std::vector<int> arrayIntersection(std::vector<int>& a, std::vector<int>& b)
{
	std::sort(a.begin(), a.end());
	std::sort(b.begin(), b.end());

	std::vector<int> result;
	std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result) );
	
	return result;
}

1. sort one array
2. each element from other array binary search in sorted array
o(nlog n)

@ Anonymous on August 28 :
Is that what you gathered from this thread after going through all the solutions?
Shame on you :-o You suck man.

Sort the arrays and merging logic it using 2 pointers.If the elements are equal print it.

308 /*function to print the intersectio of two arrays
309 len1= len of a,len2= len of b */
310 
311 void intersection(int *a, int*b, int len1, int len2) {
312         /*sort the arrays*/
313         sort_array(a,0,len1);
314         sort_array(b,0,len2);
315 
316         while (len1>=0 && len2>=0){
317 
318                 if(a[len1] > b[len2])
319                         len1--;
320                 else if (a[len1] < b[len2])
321                         len2--;
322                 else{
323                         printf("%d ",a[len1]);
324                         len1--;
325                         len2--;
326 
327                 }
328 
329         }

Are the arrays already sorted or not sorted. Can u give more details, whether space is an issue ?

public void find_intersection_of_two_Int_arrays(int[] arr1, int[] arr2)
        {
            int i = 0, j = 0, k = 0;

            ArrayList aL = new ArrayList();

            for (i = 0; i < arr1.Length; i++)
            {
                
                for (j = 0; j < arr2.Length; j++)
                {
                    if (arr1[i] == arr2[j])
                    {
                        aL.Add(arr1[i]);
                        Console.Write(aL[k++] + ",");

                    }
                    else
                        continue;
                }
            }

            
        }

Here's an opportunistic approach. If the arrays don't have any overlap, then the algo will have looped through each array just once. View the complete solution with comments, considerations, and test cases here - https://github.com/johndifini/javaAlgos/blob/master/ArrayIntersector.java

public static List<Integer> findIntersection(ArrayList<Integer> a, ArrayList<Integer> b) {
    // @todo Validate input (e.g. check for null & empty)

    // Data Structure Choice:
    // Since the results must be unique, let's use a Set.
    // In addition, let's use an ordered Set (TreeSet) so that we can short
    // circuit the searching if we find that the lists don't overlap.
    TreeSet<Integer> setA = new TreeSet<Integer>(a);
    TreeSet<Integer> setB = new TreeSet<Integer>(b);

    // Since we already got rid of dupes by using a set,
    // we can use a List for the results.
    // Note: We can't assume a minimum size for initialization?
    List<Integer> result = new ArrayList<Integer>();

    // If the "highest" of one set is less than the "lowest" of the other,
    // nothing to do (i.e. no overlap)
    // e.g. a=[1,2,3]; b=[4,5] or a=[11,22,33]; b=[1,1,1]
    if(setA.last() < setB.first() || setB.last() < setA.first()) {
        System.out.println("nothing for us to do");
        return result;
    }

    // For each elem in the smaller Set, check if it exists in the other set
    if(setA.size() < setB.size()) {
        for(int elem : setA) {
            if(setB.contains(elem)) {
                result.add(elem);
            }
        }
    }
    else {
        for(int elem : setB) {
            if(setA.contains(elem)) {
                result.add(elem);
            }
        }
    }

    return result;
}

// ZoomBA : Trivial 
a = [ 'this' , 'is' , 'cool' ] ; b = [ 'this' , 'is', 'nice' ]
isec = a & b // [ this, is ]

The most efficient solution of the above algorithm is using the hashset.
The algorithm will be as follows:-
1. Insert all the elements of array 1 in the hashset.
2. Next keep checking the array elements in the hashset of the second array if, the element of the second array is found in the hashset then, the current element is the intersection point of both the arrays.

Implemenatation:

#include<bits/stdc++.h>
using namespace std;
int findintersection(int arr_1[], int arr_2[], int m, int n){
    unordered_set<int> s;
    int count = 0;
    if(m >= n){
       for(int i = 0; i < m; i++){
            if(s.find(arr_1[i]) == s.end())
                s.insert(arr_1[i]);
        } 
        for(int i = 0; i < n; i++){
            if(s.find(arr_2[i]) != s.end()){
                count++;
                s.erase(arr_2[i]);
            }
        }
    }
    else{
        for(int i = 0; i < n; i++){
            if(s.find(arr_2[i]) == s.end())
                s.insert(arr_2[i]);
        }
        for(int i = 0; i < m; i++){
            if(s.find(arr_1[i]) != s.end()){
                count++;
                s.erase(arr_1[i]);
            }
        }
    }
    return count;
    
}
int main(){
    int t, n, m;
    cin>>t;
    while(t--){
        cin>>m>>n;
        int arr_1[m], arr_2[n];
        for(int i = 0; i < m; i++)
            cin>>arr_1[i];
        for(int i = 0; i < n; i++)
            cin>>arr_2[i];
        cout<<findintersection(arr_1, arr_2, m, n)<<endl;
    }
	//cout<<"Keep learning Keep growing"<<endl;
	return 0;

}