CareerCup

Given: Two arrays A[1...n] and B[1...m]

Case 1: Two arrays sorted Solution is O(m+n) - Linear

Case 2: A is sorted and B is not sorted 
   Sol 1: No Hashing - O(mlogn) - No Extra Space
   Sol 2: Hashing - O(m+n) - Using Extra Space

Case 3: Both A & B are not sorted
   Sol 1: Hash Table - O(m+n) - Extra Space
   SOl 2: Sort A - O(nlogn + mlogn)

how could it be O(n)...even if the arrays are sorted .The worst case time complexity is going to O(n2)

Loop through each item in Array A and do a binary search on Array B
So maximum time taken is O(m * log n)
m is size of A and n is size of B. no space is required, not even position of elements is changed in this case.

K2G, your solution wouldn't work for unsorted arrays.
Another approach: (independent of the order of Arrays - works for both sorted/unsorted arrays)
create a Binary Search Tree from Array A.
Now, search each element from array B. ( This is the best way to find duplicates)
BST creation - O(n)
searching m elements in a tree with n elements ( mlg n)
overall time complexity O(n + m lg n) -> m lg n

Sorting any array takes nLog(n)..

There are faster ways for...
From:)
http://forums.devarticles.com/c-c-help-52/how-to-compute-set-intersection-efficiently-59122.html
-----------
If duplicates are counted as one i.e. {1 2 3 3} = {1 2 3}:

1.) Assign a bit value for each item.
2.) Form two bit strings.
3.) Perform a bitwise & operation.
4.) Convert back into original.

e.g. {tom **** harry} n {harry harry fred}
Key: tom => 1 X 10^0
**** => 1 X 10^1
harry => 1 X 10^2
fred => 1 X 10^3

==> 0111 & 1100 => 0100
=> {harry}

Give credit or discredit to the original poster.

Code:
Assumption: Given 2 sorted arrays a, b of length len1 and len2 respectively

int m=0, n=0;
   while(m < len1 && n < len2)
   {
     if(a[m] == b[n])
     {
       printf("%d ", a[m]);
       m++;
       n++;
     }
     else if(a[m] > b[n])
     {
        n++;
     }
     else 
     {
        m++;
     }     
   }

Iteration is over the minimum of lengths of 2 arrays, so complexity is O(min(m,n))

i, j = 0, 0
a = [-9, -8, 0, 1, 4, 6]
b = [-8, -7, -6, 0, 1, 3, 5, 6]

while (i < a.size && j < b.size) do
    if a[i] == b[j]
        #puts "a[i] = #{a[i]} and b[j] = #{b[j]} Incrementing i and j"
        puts a[i]
        i += 1
        j += 1
    elsif a[i] < b[j]
        #puts "a[i] = #{a[i]} and b[j] = #{b[j]} Incrementing j"
        i += 1
    elsif b[j] < a[i]
        #puts "a[i] = #{a[i]} and b[j] = #{b[j]} Incrementing i"
        j += 1
     end
end

Put all elements of first into hashtable. For each ele in
Second array chk if it is present in table . If yes put into
Result arrray else continue.
Correct me...

One of the best algorithms for finding the intersection of two arrays when the arrays are sorted is applying binary search to find all the elements of the other array in the first array and print the elements which are common in both the arrays:

Imlemenatation:

bool binary-search(int arr[], int low, int high, int key){
	if(high >= low){
		int mid = low + (high - low) / 2;
		if(arr[mid] == key)
			return true;
		if(key > arr[mid])
			return binary-search(arr, mid + 1, high, key);
		else
			return binary-search(arr, low, mid - 1, key);
	}
	return false;
}
int main{
	for(int i = 0; i < m; i++){
		if(binary-search(arr_1, 0, n, arr_2[i]) == true)
			cout<<arr_2[i]<<" ";
	}

Time complexity will be O(logn).
Space complexity will be O(1).

And while the array is not sorted then we can use a hashset to find the common elements.

sorted:
O(N)
unsorted:
first sort O(log(n))
Then O(N)
So totally O(n)

is that correct?