Intersection of Two Sorted Arrays

Given two sorted arrays arr1[] and arr2[], return the intersection of both arrays.

The intersection is the set of elements that are common in both arrays. It must not contain duplicates. If there is no common element, return an empty array.

Constraints:

1 <= arr1.size(), arr2.size() <= 10^5
1 <= arr1[i], arr2[i] <= 10^6

Example 1:

Input: arr1[] = [1, 2, 3, 4], arr2[] = [2, 4, 6, 7, 8]

Output: [2, 4]

Explanation: 2 and 4 are only common elements in both the arrays.

Example 2:

Input: arr1[] = [1, 2, 2, 3, 4], arr2[] = [2, 2, 4, 6, 7, 8]

Output: [2, 4]

Explanation: 2 and 4 are the only common elements.

Example 3:

Input: arr1[] = [1, 2], arr2[] = [3, 4]

Output: []

Explanation: No common elements.

Brute Force

For every value in arr1, search the whole of arr2 to see if it is there.

Go through arr1 one value at a time.
If the value is the same as the last value in result, skip it. arr1 is sorted, so a duplicate sits right next to its copy.
Otherwise, scan arr2 from the start.
If you find the value, add it to result and stop scanning.
Return result.

This works, but for each value of arr1 we may scan all of arr2. It ignores that both arrays are sorted.

class Solution {
    public:
    vector<int> intersection(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        int m = arr2.size();
        vector<int> result;

        for (int i = 0; i < n; i++) {
            if (!result.empty() && result.back() == arr1[i]) {
                continue;
            }

            for (int j = 0; j < m; j++) {
                if (arr1[i] == arr2[j]) {
                    result.push_back(arr1[i]);
                    break;
                }
            }
        }

        return result;
    }
};

Time: O(n * m). For each value of arr1, we may scan all of arr2.
Space: O(1) extra, not counting the output array.

Optimal Approach: Two Pointers

Both arrays are sorted, so we can walk through them together with one pointer on each.

We use:

i: pointer on arr1.
j: pointer on arr2.

At each step, compare arr1[i] and arr2[j]:

arr1[i] < arr2[j]: arr1[i] is too small. It cannot be in arr2 anymore. Move i forward.
arr1[i] > arr2[j]: arr2[j] is too small. Move j forward.
Equal: we found a common value. Add it to result only if result is empty or its last value is different (this skips duplicates). Move both pointers forward.

Stop when either array is finished, because nothing more can match.

class Solution {
    public:
    vector<int> intersection(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        int m = arr2.size();
        int i = 0;
        int j = 0;
        vector<int> result;

        while (i < n && j < m) {
            if (arr1[i] < arr2[j]) {
                i++;
            } else if (arr1[i] > arr2[j]) {
                j++;
            } else {
                if (result.empty() || result.back() != arr1[i]) {
                    result.push_back(arr1[i]);
                }

                i++;
                j++;
            }
        }

        return result;
    }
};

Complexity

Time: O(n + m)

Every step moves at least one pointer forward, so each element of both arrays is looked at at most once.

Space: O(1) extra

Besides the output array, we only use the pointers i and j. The output holds at most min(n, m) values.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch

"The simple idea is to take each value of the first array and search the whole second array for it, skipping a value if it is the same as the last one I added, so there are no duplicates. That is O of n times m time, because I may scan the second array for every value. A better way is two pointers, since both arrays are sorted. I keep one pointer on each array and compare the two front values. If the first is smaller, I move the first pointer. If the second is smaller, I move the second pointer. If they are equal, I found a common value, so I add it to the result unless it is the same as the last value I added, which avoids duplicates, and then I move both pointers. I stop as soon as one array is finished. The time complexity is O of n plus m and the extra space complexity is O of 1, not counting the output array."

Next TopicMove Zeroes