Union of Two Sorted Arrays

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

The union is the set of distinct elements that are present in either of the arrays.

Constraints:

• 1 <= a.size(), b.size() <= 10^5
• -10^9 <= a[i], b[i] <= 10^9

Brute Force

Put every value from both arrays into an ordered set. A set keeps only one copy of each value, and an ordered set keeps them sorted.

1. Create an empty ordered set.
2. Insert every value of a into the set.
3. Insert every value of b into the set.
4. Copy the values from the set into the result, from smallest to largest.

This works, but it ignores that both arrays are already sorted. The set has to sort the values again, and it needs extra memory to hold them.

class Solution {
    public:
    vector<int> findUnion(vector<int>& a, vector<int>& b) {
        set<int> uniqueValues;

        for (int value : a) {
            uniqueValues.insert(value);
        }

        for (int value : b) {
            uniqueValues.insert(value);
        }

        vector<int> result;

        for (int value : uniqueValues) {
            result.push_back(value);
        }

        return result;
    }
};

• Time: O((n + m) log(n + m)). Ordering the values costs O(log) per insert.
• Space: O(n + m). The set can hold every value.

Optimal Approach: Two Pointers

Both arrays are already sorted. So the smallest remaining value is always at the front of one of the two arrays. This is the same idea as merging two sorted lists, with one extra rule: skip duplicates.

We use:

• i: pointer on array a.
• j: pointer on array b.
• result: the union we are building.

The duplicate rule: before adding a value, check the last value in result. If it is the same, skip it. Because everything arrives in sorted order, any duplicate is always right next to its copy.

Steps:

1. Start i = 0 and j = 0.
2. While both arrays have elements, pick the smaller of a[i] and b[j] and move that pointer forward.
3. Add the picked value to result only if result is empty or its last value is different.
4. When one array is finished, go through the rest of the other array with the same duplicate rule.
5. Return result.

class Solution {
    public:
    vector<int> findUnion(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        int i = 0;
        int j = 0;
        vector<int> result;

        while (i < n && j < m) {
            int value;

            if (a[i] <= b[j]) {
                value = a[i];
                i++;
            } else {
                value = b[j];
                j++;
            }

            if (result.empty() || result.back() != value) {
                result.push_back(value);
            }
        }

        while (i < n) {
            if (result.empty() || result.back() != a[i]) {
                result.push_back(a[i]);
            }

            i++;
        }

        while (j < m) {
            if (result.empty() || result.back() != b[j]) {
                result.push_back(b[j]);
            }

            j++;
        }

        return result;
    }
};

Complexity

How to Explain It in an Interview