Union of two sorted arrays

Given two sorted arrays nums1 and nums2, return an array that contains the union of these two arrays. The elements in the union must be in ascending order.

The union of two arrays is an array where all values are distinct and are present in either the first array, the second array, or both.

Brute Force: hashset#

Insert all elements from both arrays into an ordered set (std::set). The set automatically deduplicates and maintains sorted order, so we can directly convert it to a result vector. The downside is that set insertions take O(log k) each (where k is the number of unique elements), and we pay O(k log k) to build the set — missing the linear opportunity that the sorted property of both inputs provides.

class Solution {
public:
    vector<int> unionArray(vector<int>& nums1, vector<int>& nums2) {
        set<int> Union;

        for(int i=0;i<nums1.size();i++){
            Union.insert(nums1[i]);
        }
        for(int i=0;i<nums2.size();i++){
            Union.insert(nums2[i]);
        }

        vector<int> result(Union.begin(), Union.end());

        return result;
    }
};

Time Complexity: O(n + m + klogk), where k -> unique ele

Space Complexity: O(k)

Optimal Approach#

Use a two-pointer merge similar to the merge step in merge sort. Advance pointer i through nums1 and pointer j through nums2, always picking the smaller front element and appending it to the result only if it differs from the last element added (to skip duplicates). After one array is exhausted, drain the remaining elements of the other, again skipping duplicates. Because both arrays are already sorted, no set is needed — we get O(n + m) time and the result itself accounts for the O(n + m) output space.

class Solution {
public:
    vector<int> unionArray(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        int m = nums1.size();
        int n = nums2.size();

        int i=0, j=0;

        while(i<m && j<n){
            if(nums1[i] <= nums2[j]){
                if(result.size()==0 || result.back() != nums1[i]){
                    result.push_back(nums1[i]);
                }
                i++;
            }else{
                if(result.size()==0 || result.back() != nums2[j]){
                    result.push_back(nums2[j]);
                }
                j++;
            }
        }

        while(i<m){
            if(result.back() != nums1[i]){
                result.push_back(nums1[i]);
            }
            i++;
        }

        while(j<n){
            if(result.back() != nums2[j]){
                result.push_back(nums2[j]);
            }
            j++;
        }

        return result;
    }
};

Time Complexity: O(n + m),

Space Complexity: O(n + m)