Union of Two Sorted Arrays

Problem

Given two sorted arrays, return their union as a sorted array with no duplicates.

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

Python Solution

def union_sorted(arr1, arr2):
    i, j = 0, 0
    result = []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            if not result or result[-1] != arr1[i]:
                result.append(arr1[i])
            i += 1
        elif arr2[j] < arr1[i]:
            if not result or result[-1] != arr2[j]:
                result.append(arr2[j])
            j += 1
        else:
            if not result or result[-1] != arr1[i]:
                result.append(arr1[i])
            i += 1
            j += 1
    while i < len(arr1):
        if not result or result[-1] != arr1[i]:
            result.append(arr1[i])
        i += 1
    while j < len(arr2):
        if not result or result[-1] != arr2[j]:
            result.append(arr2[j])
        j += 1
    return result

C++ Solution

vector<int> unionSorted(vector<int>& arr1, vector<int>& arr2) {
    int i = 0, j = 0;
    vector<int> result;
    while (i < arr1.size() && j < arr2.size()) {
        int val = (arr1[i] <= arr2[j]) ? arr1[i] : arr2[j];
        if (result.empty() || result.back() != val) result.push_back(val);
        if (arr1[i] <= arr2[j]) i++;
        else j++;
    }
    while (i < arr1.size()) {
        if (result.empty() || result.back() != arr1[i]) result.push_back(arr1[i]);
        i++;
    }
    while (j < arr2.size()) {
        if (result.empty() || result.back() != arr2[j]) result.push_back(arr2[j]);
        j++;
    }
    return result;
}

Java Solution

class Solution {
    public List<Integer> unionSorted(int[] arr1, int[] arr2) {
        int i = 0, j = 0;
        List<Integer> result = new ArrayList<>();
        while (i < arr1.length && j < arr2.length) {
            int val = (arr1[i] <= arr2[j]) ? arr1[i] : arr2[j];
            if (result.isEmpty() || result.get(result.size() - 1) != val) result.add(val);
            if (arr1[i] <= arr2[j]) i++; else j++;
        }
        while (i < arr1.length) {
            if (result.isEmpty() || result.get(result.size() - 1) != arr1[i]) result.add(arr1[i]);
            i++;
        }
        while (j < arr2.length) {
            if (result.isEmpty() || result.get(result.size() - 1) != arr2[j]) result.add(arr2[j]);
            j++;
        }
        return result;
    }
}

Complexity

Time: O(m + n) — each array is scanned once with two pointers, merge-style. Space: O(m + n) for the output list in the worst case, where no elements overlap.