Topics › Arrays › Easy

Union of two sorted arrays

Easy TUF ID 48 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given two arrays a and b, each sorted in non-decreasing order and each possibly containing duplicates. Return their union: every distinct value that appears in a or in b (or both), in ascending order, with no repeats.

Constraints: 0 ≤ n, m ≤ 10^5, values fit in a 32-bit signed integer.

Example 1

a = [1, 2, 3, 4, 5], b = [2, 3, 4, 4, 5]
union = [1, 2, 3, 4, 5]          // 2..5 occur in both; each appears once

Example 2

a = [1, 1, 2, 2, 3], b = [2, 3, 3, 4]
union = [1, 2, 3, 4]             // duplicates inside a single array are removed too

Example 3

a = [], b = [3, 3, 7]
union = [3, 7]                   // the union with an empty array is the other array, de-duplicated

Two facts do all the work: the inputs are sorted, so equal values are adjacent and the smallest remaining value is always at the front of one of the arrays; and the output must be distinct, which with sorted output means “do not write a value equal to the one you just wrote”.

Approach 1: Brute force, a sorted set

Intuition. Forget that the inputs are sorted. A TreeSet stores each value once and iterates in ascending order, so adding every element of both arrays and reading the set back gives the union directly. The container does the de-duplication and the ordering; we do nothing clever.

Algorithm.

1. Add all of a, then all of b, to a TreeSet<Integer>.
2. Allocate an array of the set’s size and copy the set into it in iteration order.

static int[] bruteForce(int[] a, int[] b) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int x : a) set.add(x);
    for (int x : b) set.add(x);
    int[] result = new int[set.size()];
    int i = 0;
    for (int x : set) result[i++] = x;
    return result;
}

Complexity. Time O((n + m) log(n + m)): each insertion is a balanced-tree operation. Space O(n + m) for the set, with every int boxed into an Integer.

It is correct and short, but it throws away the sortedness we were given and pays a logarithm per element to rediscover it.

Approach 2: Optimal, merge with de-duplication

Intuition. This is the merge step of merge sort with one extra rule. Keep an index into each array. At every step the smallest unconsumed value overall is either a[i] or b[j], so take the smaller one (on a tie, take a[i] and leave b[j] for the next round). Before writing it to the output, compare it with the last value written; if they are equal, skip it. Because the output is produced in ascending order, “equal to the last value written” is the only way a duplicate can arise, whether it comes from the same array or from the other one.

When one array runs out, the rest of the other array is appended with the same “skip if equal to last written” test, which also removes duplicates within that tail.

Algorithm.

1. Allocate buf of size n + m, the largest the union can be. Set i = j = k = 0.
2. While both arrays have elements: pick x = a[i] if a[i] <= b[j] (advance i), else x = b[j] (advance j). If k == 0 or buf[k - 1] != x, write buf[k++] = x.
3. Append the leftovers of a, then of b, applying the same test.
4. Return buf trimmed to length k.

static int[] optimal(int[] a, int[] b) {
    int n = a.length, m = b.length;
    int[] buf = new int[n + m];                  // upper bound: no value shared, no duplicates
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        int x;
        if (a[i] <= b[j]) x = a[i++];            // ties take a's copy; b's copy is skipped on the next round
        else x = b[j++];
        if (k == 0 || buf[k - 1] != x) buf[k++] = x;
    }
    while (i < n) {
        if (k == 0 || buf[k - 1] != a[i]) buf[k++] = a[i];
        i++;
    }
    while (j < m) {
        if (k == 0 || buf[k - 1] != b[j]) buf[k++] = b[j];
        j++;
    }
    return Arrays.copyOf(buf, k);
}

Dry run on a = [1, 1, 2, 2, 3], b = [2, 3, 3, 4]:

k = 4, result [1, 2, 3, 4].

Complexity. Time O(n + m): every step advances i or j, so there are exactly n + m steps. Space O(n + m) for the output, which is unavoidable since the union itself can be that large; beyond the output only three indices are used.

The k == 0 || guard is the one piece of care needed: buf[-1] would throw before anything has been written. Short-circuit evaluation ensures buf[k - 1] is only read when k > 0.

Why does the single comparison with buf[k - 1] suffice to catch duplicates from both arrays? Because the output is non-decreasing. If a value v has already been written, every later candidate is ≥ v; the moment a later candidate equals v, the last written value is still v (nothing larger has appeared yet), so the test catches it. Once something larger than v is written, no v can appear again.

Edge cases and pitfalls

• Both arrays empty. The buffer has size 0, no loop runs, Arrays.copyOf(buf, 0) returns an empty array.
• One array empty. The main loop is skipped and the leftover loop de-duplicates the non-empty array on its own: [] and [3, 3, 7] give [3, 7].
• All values equal. [5, 5, 5] and [5] give [5]; only the very first candidate passes the k == 0 test.
• Duplicates straddling the two arrays. A value that ends a and starts b is caught by the leftover loop’s comparison with buf[k - 1]; the test does not reset between phases.
• Ties. Taking a[i] on a tie (<=) rather than both at once keeps the code uniform; the b copy is rejected on the next iteration. Advancing both indices on a tie is also correct but needs a separate branch.
• Returning the full buffer. The buffer is sized n + m but only k slots are meaningful; forgetting Arrays.copyOf(buf, k) returns trailing zeros that look like real elements.
• Unsorted input. The merge relies on sortedness. If the arrays are not sorted, sort them first (O(n log n)) or use the set approach.
• Symmetry. union(a, b) must equal union(b, a); the tests call optimal both ways.
• Intersection is the mirror problem. Keep a value only when a[i] == b[j] (advancing both), and still de-duplicate against the last written value.

Related problems

• Remove duplicates from Sorted array is the single-array version of the “skip if equal to last written” rule.
• Merge Sorting is where the two-index merge comes from.
• Merge two sorted arrays without extra space asks for the merge (keeping duplicates) under a tight memory limit.
• Find missing number is the next problem on the sheet.