CareerCup

there is an O(log(N)) solution here

What I know of is O(n). All ears for O(log(n))...

use two pointers for both array. If equal, move two pointers. Otherwise, move forward the smaller one.
Complexity: nlogn (for sorting) + o(n)

its already sorted array, so the complexity would be o(n)

how can it be O(log n) ??

what if all the elements in both the arrays are same ?? then can it be done in O(log n) ?? please let me know if i m missing something....

You can construct a hash table out of the first array and search which all elements of the second array are present in it; in which case the complexity will be o(n). I don't think there is at all an o(log n) solution.

since both the arrays are sorted could we do parallel binary search on both the arrays???
Say suppose the 2 arrays were A[n] and B[m];
mida = 0+n/2;
midb = 0+m/2;
if A[mida] == B[midb] Return the value
else if A[mida] < B[midb] binary search on mida+1 to n and 0 to midb-1
else binary search on 0 to mida-1 and midb+1 to m

this works provided only one number intersection exists.. ie there is only one number in common in both the arrays..

any comments??

I think binary search will work, since both arrays are sorted..

For example, if 2 arrays are [ 1 2 3 5 7 8 ] and [5 7 8 ]

We split Array 1 into two halves [1 2 3] [5 7 8]. Compare first element of array 2, 5 with last element of first half(3) and first elemet of second half(5).
If they are equal to either one intersection is found, else compare and eliminate one half and perform similar operation on the current half and repeat till intersection is found.

I am not sure, if there are any cases when this would not work.

I think binary search will work, since both arrays are sorted..

For example, if 2 arrays are [ 1 2 3 5 7 8 ] and [5 7 8 ]

We split Array 1 into two halves [1 2 3] [5 7 8]. Compare first element of array 2, 5 with last element of first half(3) and first elemet of second half(5).
If they are equal to either one intersection is found, else compare and eliminate one half and perform similar operation on the current half and repeat till intersection is found.

I am not sure, if there are any cases when this would not work.

@radhika your solution is o(n logn ) but o(n) solution exist ....as told by sumeet

Radhika tujhe pakad pakad ke chodu ;)

There are 3 solutions:
Here n is First Array Count and m is Second Array Count.
1. Brute Force Case : (Really Bad) o(nm).
You will use two loops and find the intersection.

2. a.HashTable/Hash Set Case: O(n+m) but space complexity is O(n)
b. Without hash w can also iterate using while loop since both arrays are sorted. In that case, time complexity is O(n+m)

3. Using Binary Search: O(nlogm)

If the array size is very large. This solution is the Winner.
Loop the firstArray and find the each element in Second array by using BST.

For example, if the input arrays are:
a[] = {1, 3, 4, 5, 7}
b[] = {2, 3, 5, 6}

Intersection is result[] = {3,5} 

Algorithm to solve this : 
1. Start with two loops starting at positions a [0] and b[0].
2. If a[i] is less than b[j] then increment a[i] and compare again 
3. If a[i] is greater that b[j] then increment b[j] 
4. If a[i] == b[j] then store the value in result[] 
5. Else we can say that the arrays have no intersecting values 

Code : 

#include<stdio.h>
 
/* Function prints Intersection of a[] and b[]
   m is the number of elements in a[]
   n is the number of elements in b[] */
int arrayIntersection(int a[], int b[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(a[i] < b[j])
      i++;
    else if(b[j] < a[i])
      j++;
    else /* if a[i] == b[j] */
    {
      printf(" %d ", b[j++]);
      i++;
    }
  }
}
 
/* Driver program to test above function */
int main()
{
  int a[] = {1, 2, 4, 5, 6};
  int b[] = {2, 3, 5, 7};
  int m = sizeof(a)/sizeof(a[0]);
  int n = sizeof(b)/sizeof(b[0]);
  arrayIntersection(a, b, m, n);
  getchar();
  return 0;
}

Time complexity would be O(m+n) 

Method 2: 
I could also think of another solution but i dont really know how it will span out to be 

Algo2 : 
1. Create a BST with array1. 
2. loop with array2 and try to insert each element of array2 into the BST as new node 
3. If the node with the value is already present put that into the result array / print it.