CareerCup

bit maps is one probable solution if the data range is small, other wise it takes lots of space

time complexity O(m+n)

For Intersection of two sorted arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.

int printIntersection(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      i++;
    else if(arr2[j] < arr1[i])
      j++;
    else /* if arr1[i] == arr2[j] */
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }
}

Time Complexity: O(m+n) for sorted arrarys.

For unsorted arrays Time complexity will be O(mlogm + nlogn)

Note: Sorting phase takes O(nlogn)

Comparison only algorithms have proven lower bounds which are O(K log K), where K = min (m,n).

If the question instead was to solve the problem for two sorted arrays, there is a simple comparison-based O(m+n) time algorithm whose logic is very similar to the "merge" step of mergesort. Step through the two arrays in the same way that the merge algorithm does, and when the next element from array1 is equal to the next element from array2, add the common number to a list of results.

For two unsorted arrays, you can solve using a hash set, but this is O(m+n) only in the expectation and not in the worst case. You can solve the problem in worst-case O(m+n+R) time where R is the range of the numbers, if you also have O(R) space, by using a bitset. Finally, if you are programming in a language that does not initialize memory, you can solve the problem with O(R) space and O(m+n) (no R) time by combining the bitset approach with uninitialized memory tricks.

If space is not an issue we can do:
1.Hash the elements of the smaller array based on their values -> O(m) time and O(m) space
2. Search the elements of larger array in the hash and if exists keep it -> O(n)

Hence, we achieve a O(n) time with the addition of O(m) space where n>m. Apparently, it would be a O(n) time and space if m=n

can someone please explain in detail the solution with bitmaps

public static int findIntersection(int[] a, int[] b)
{
quickSort(a);
quickSort(b);
int N = a.length;
int M = b.length;
int i = 0;
int j = 0;
while(i<N && j<M)
{
if (a[i]<b[j]) i++;
else if (a[i]>b[j]) j++;
else if(a[i] == b[j]) break;
else return -1;
}
return a[i];
}


public static void main(String[] args)
{

int[] a = {5,1,99,2,4};
int[] b = {3,5,7,23,66,100};
System.out.println(findIntersection(a,b));
}

Suppose we have 2 arrays of size n & m respectively, now sort the array of size n with complexity O(n log n) , then look for every element of the second array (size m) in the first array (size n) then the complexity will be O(m log(n))
Will this be considered acceptable ?

If each array has only distinct elements, then:
- XOR all elements of one array.. Let's say it is x.
- For each element of the second array, find (x XOR element). If that is 0, this element is in the intersection list.