Question Daily

Intersection of Two Sorted Arrays

Given two sorted arrays a[] and b[], where each array may contain duplicate elements, return the elements in the intersection of the two arrays in sorted order.

Note: Intersection of two arrays can be defined as the set containing distinct common elements that are present in both of the arrays.

Solve Logic:

1. Initialize Two Pointers: Start with two pointers, i = 0 for array a and j = 0 for array b. Create an empty list (vector) to store your results.
2. Iterate through Arrays: While both pointers are within the bounds of their respective arrays (i < a.size() and j < b.size()):

   • Case 1: a[i] < b[j]

     Because array b is sorted, the value a[i] cannot appear later in b. So, move pointer i forward (i++).

   • Case 2: b[j] < a[i]

     Similarly, the value b[j] cannot appear later in a. Move pointer j forward (j++).

   • Case 3: a[i] == b[j]

     We've found a common element!

     • Handle Duplicates: Check if this element was already added to your result list (compare it with the last element added). If it’s new, add it to the results.
     • Then, move both pointers forward (i++ and j++) to continue the search.
3. Return Result: Once the loop finishes, return the result list.

Solve code

class Solution {
  public:
    vector<int> intersection(vector<int>& a, vector<int>& b) {
        vector<int> ans;
        int n = a.size();
        int m = b.size();
        int i = 0, j = 0;
        
        while (i < n && j < m) {
            if (a[i] < b[j]) {
                // Element in 'a' is smaller, skip it
                i++;
            } else if (b[j] < a[i]) {
                // Element in 'b' is smaller, skip it
                j++;
            } else {
                // Found a common element (a[i] == b[j])
                // Check if it's the first element or a new distinct element
                if (ans.empty() || ans.back() != a[i]) {
                    ans.push_back(a[i]);
                }
                // Move both pointers forward
                i++;
                j++;
            }
        }
        return ans;
    }
};

Complexity

• Time Complexity: , where  and  are the sizes of the two arrays. We traverse each array at most once.

  O(n+m)
  

• Space Complexity:  for storing the result if all elements are common and distinct. If excluding output space, it's O(1)

  O(min(n,m))