Intersection of Two Sorted Arrays

EPI

Description:

Given two sorted arrays, find their intersection.

Example:

Input:
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6} 
Output:
Intersection : {3, 5}

Idea:

arr1 size m, arr2 size n. This algo complexity is O(m+n).

If n is very large, then for each element in arr1, binary search to check existance in arr2. Time complexity is O(m*lg n).

Code:

vector<int> findIntersection(vector<int> A, vector<int> B) {
  vector<int> intersection;
  int n1 = A.size();
  int n2 = B.size();
  int i = 0, j = 0;
  while (i < n1 && j < n2) {
    if (A[i] > B[j]) {
      j++;
    } else if (B[j] > A[i]) {
      i++;
    } else {
      intersection.push_back(A[i]);
      i++;
      j++;
    }
  }
  return intersection;
}

if duplicate is not allowed

    else {
        if( intersection.empty() || A[i]!=intersection.back() ){
            intersection.push_back(A[i]);           
        }
        i++;
        j++;
    }