Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Union of Two Sorted Arrays

Merge two sorted arrays into a sorted list of distinct values with two pointers.

MediumArraysPattern: two pointers

Problem statement

Return the sorted union of two sorted integer arrays. Each value should appear once in the result.

For [1, 1, 3, 5] and [2, 3, 4], return [1, 2, 3, 4, 5].

Constraints & requirements

INPUT
Two sorted integer arrays
RETURN
A sorted list of distinct values
TARGET
One coordinated pass

Examples 3 test cases

  1. Example 1 Overlapping values

    Input
    [1, 1, 3, 5] and [2, 3, 4]
    Output
    [1, 2, 3, 4, 5]

    Checks merging and duplicate removal.

  2. Example 2 One empty input

    Input
    [] and [2, 2, 4]
    Output
    [2, 4]

    Checks the remaining-elements loop.

  3. Example 3 Same values

    Input
    [1, 2] and [1, 2]
    Output
    [1, 2]

    Checks duplicates across both arrays.

Hints Optional

Hints become more specific one step at a time.
01Compare the smallest remaining values

Because both inputs are sorted, the next result value must be at one of the two pointers.

02Move at least one pointer

Take the smaller current value. When values are equal, either consume both now or safely skip the duplicate later.

03Keep the result distinct

Append a candidate only when it differs from the last value already added.

How to think before coding

Before choosing a data structure, use the given sorted order. Each pointer exposes its input’s smallest unread value; the smaller front must be the next candidate overall. Advance that pointer even when the candidate is a duplicate. Save a candidate only if it differs from the last saved value, and remember to drain the remaining input after one ends.

Brute force and the improvement

Insert both arrays into a balanced sorted set: O((n + m) log(n + m)) time and O(n + m) storage in the worst case. Concatenate, sort, and remove duplicates has the same time bound and needs a combined working collection. These approaches also support unsorted input, but merging uses the already sorted order with O(1) auxiliary state, excluding the returned list.

Intuition

The smallest unprocessed value must be at one of the two current pointers. Add that value when it differs from the last value in the result, then move the matching pointer.

Java solution

Java
import java.util.ArrayList;
import java.util.List;

public static List<Integer> sortedUnion(int[] first, int[] second) {
    // This list is required output storage, not a copy of the inputs.
    List<Integer> union = new ArrayList<>();
    int left = 0;
    int right = 0;

    while (left < first.length && right < second.length) {
        int value;
        // The smaller front value is the smallest unread value overall.
        if (first[left] <= second[right]) {
            value = first[left++];
        } else {
            value = second[right++];
        }
        addIfNew(union, value); // Read equal candidates twice but save them once.
    }

    // One input ended. Drain the other, still skipping duplicates.
    while (left < first.length) {
        addIfNew(union, first[left++]);
    }
    while (right < second.length) {
        addIfNew(union, second[right++]);
    }
    return union;
}

private static void addIfNew(List<Integer> values, int value) {
    // Sorted traversal makes equal candidates adjacent.
    if (values.isEmpty() || values.get(values.size() - 1) != value) {
        values.add(value);
    }
}

Dry run

Numbered illustrated dry run for Union of Two Sorted Arrays; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For [1, 1, 3, 5] and [2, 3, 4], take the smaller front value each time.

Candidate source Value Append? Result
First 1 Yes, result empty [1]
First 1 No, duplicate [1]
Second 2 Yes [1, 2]
First 3 Yes [1, 2, 3]
Second 3 No, duplicate [1, 2, 3]
Second 4 Yes [1, 2, 3, 4]
First, after second ends 5 Yes [1, 2, 3, 4, 5]

Each step consumes one input value, so neither pointer can get stuck.

Complexity

Time is O(n + m). The result uses O(n + m) space in the worst case.

Common mistake

Using a set and sorting the result works, but it ignores the fact that both inputs are already sorted. The two pointer solution uses that information directly.

Practice next

Next lessonLongest Subarray with Sum K

Move from pointer state to prefix history.

Back to Arrays →