Union of Two Sorted Arrays

Union of Two Sorted Arrays is a classic two-pointer warm-up. Because the inputs are already sorted, you can walk both at once and produce the sorted, duplicate-free union in a single linear pass — no extra sorting, no hash set required.

The slow way first

The lazy approach: dump both arrays into a set, then sort the set. That works and is easy to write, but it throws away the sorted order you were handed. Sorting costs O((n + m) log(n + m)), and the set uses extra hashing overhead you do not need.

The question to ask: both arrays are already sorted — how do I exploit that? When two lists are sorted, you can merge them by always looking at the two front elements and taking the smaller one. That is the merge step of merge sort, and it runs in O(n + m).

The idea: walk both with two pointers

Keep an index i into a and j into b. Compare a[i] and b[j]:

• If they are equal, that value belongs in the union once. Append it and advance both pointers (this skips the duplicate).
• If a[i] is smaller, append it and advance only i.
• Otherwise b[j] is smaller, so append it and advance only j.

When one array runs out, append whatever is left of the other.

The key insight: because both arrays are sorted, the smaller of the two fronts is the smallest value not yet placed — so appending it keeps the result sorted automatically.

Walk through it

Step through the animation. Pointers i and j start at the front of each row. The first three comparisons are ties (1, 2, 3), so each is appended once and both pointers move. Then 4 and 5 from a win their comparisons against 6. Once a is exhausted, the leftover tail of b — 6 and 7 — is appended directly.

Pseudocode

out = empty list
i = 0, j = 0
while i < len(a) and j < len(b):
    if a[i] == b[j]:        # shared value: take once
        append a[i]; i += 1; j += 1
    elif a[i] < b[j]:
        append a[i]; i += 1
    else:
        append b[j]; j += 1
append the rest of a (if any)
append the rest of b (if any)
return out

The Python solution

def union(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    while i < len(a): out.append(a[i]); i += 1
    while j < len(b): out.append(b[j]); j += 1
    return out

• out collects the union; i and j are the two read positions, both starting at 0.
• The while loop runs while both arrays still have elements to compare.
• The equal branch (lines 5 to 6) appends the shared value once and advances both pointers, which is how duplicates across the two arrays are skipped.
• The elif and else branches append the smaller front and advance just that pointer.
• After the loop, one array may still have a tail. The two trailing while loops drain whichever array is left — only one of them ever runs.

Complexity

We touch each element of each array at most once, so the time is linear in the combined length. The only extra space is the output list itself (the union of both arrays), giving O(n + m) space.

When this pattern shows up

Practice