thesarfo

Reference

Union of Two Sorted Arrays

Combining two sorted arrays into a deduplicated, sorted union using a set vs. a two-pointer merge.

views 0

Combine two sorted arrays into a deduplicated, sorted union. [1,1,2,3,4,5] + [2,3,4,4,5,6] → [1,2,3,4,5,6].

Brute force: dump both arrays into a set, then copy into a result array.

Optimal — two pointers, since both inputs are already sorted: advance whichever pointer is smaller, only appending to the result if it differs from the last appended value (to dedupe).

vector<int> sortedArray(vector<int> a, vector<int> b) {
    int n1 = a.size();
    int n2 = b.size();
    int i = 0, j = 0;
    vector<int> unionArr;


    while(i < n1 && j < n2){
        if (a[i] <= b[j]){
            if(unionArr.size() == 0 || unionArr.back() != a[i]){
                unionArr.push_back(a[i]);
            }
            i++;
        } else{
            if(unionArr.size() == 0 || unionArr.back() != b[j]){
                unionArr.push_back(b[j]);
            }
            j++;
        }
    }


    while (i < n1) {
        if (unionArr.empty() || unionArr.back() != a[i]) unionArr.push_back(a[i]);
        i++;
    }


    while (j < n2) {
        if (unionArr.empty() || unionArr.back() != b[j]) unionArr.push_back(b[j]);
        j++;
    }


    return unionArr;
}