Find the Union and Intersection of the two sorted arrays

The problem, simply

You get two arrays A (length m) and B (length n), each sorted from small to big. They may contain repeats.

Give back two sorted lists, each without repeats:

• The union: every number that is in A or in B (or both).
• The intersection: every number that is in both A and B.

A story to remember it

Picture it

Examples

Way 1: the simple way

Throw everything into sets and let them remove the repeats.

1. Union: put every number of A and B into a sorted set (TreeSet).
2. Intersection: put A into a hash set, then keep the numbers of B that are in it (in a sorted set, so each appears once and in order).

class Solution {
    public List<Integer> union(int[] a, int[] b) {
        Set<Integer> all = new TreeSet<>();          // sorted, no repeats
        for (int x : a) all.add(x);
        for (int x : b) all.add(x);
        return new ArrayList<>(all);
    }

    public List<Integer> intersection(int[] a, int[] b) {
        Set<Integer> inA = new HashSet<>();
        for (int x : a) inA.add(x);
        Set<Integer> both = new TreeSet<>();
        for (int x : b) if (inA.contains(x)) both.add(x);
        return new ArrayList<>(both);
    }
}

How long it takes: each insert into a sorted set costs O(log(m + n)), so O((m + n) log(m + n)). Extra room: the sets, O(m + n). It ignores the fact that the input is already sorted.

Way 2: the clever way

Walk both arrays at once with two fingers, like the merge step of merge sort.

1. i = 0 on A, j = 0 on B.
2. If A[i] < B[j]: A[i] is not in B (B has only bigger numbers left). Add it to the union. Move i.
3. If A[i] > B[j]: same for B[j]. Move j.
4. If they are equal: add the number to the union and to the intersection. Move both.
5. When one array runs out, copy the rest of the other into the union.
6. Before adding to a list, check that it is not the same as the last number in that list. This removes repeats.

class Solution {
    public List<List<Integer>> unionAndIntersection(int[] a, int[] b) {
        List<Integer> union = new ArrayList<>(), both = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) addOnce(union, a[i++]);         // only in A
            else if (a[i] > b[j]) addOnce(union, b[j++]);    // only in B
            else {                                           // in both
                addOnce(union, a[i]);
                addOnce(both, a[i]);
                i++; j++;
            }
        }
        while (i < a.length) addOnce(union, a[i++]);         // leftovers of A
        while (j < b.length) addOnce(union, b[j++]);         // leftovers of B
        return List.of(union, both);
    }

    private void addOnce(List<Integer> list, int x) {
        if (list.isEmpty() || list.get(list.size() - 1) != x) list.add(x);  // skip repeats
    }
}

How long it takes: every step moves at least one finger, so at most m + n steps, O(m + n). Extra room: two fingers, O(1) besides the answer lists.

Watch out for

• Repeats: the "same as the last one written" check works only because the numbers come out in sorted order.
• list.get(...) != x compares an Integer with an int, so Java unboxes and compares numbers. Comparing two Integer objects with != would be a bug.
• If the problem wants repeats kept in the intersection (each match counted), drop the check for that list: [4, 4] and [4, 4, 4] then share [4, 4].

What interviewers ask next

• The arrays are not sorted? Sort them first (O(m log m + n log n)), or use hash sets (O(m + n) time, O(m + n) room).
• One array is tiny and the other is huge? For each number of the small array, binary search the big one: O(m log n), much better than O(m + n) when m is tiny.
• Intersect k sorted arrays? Intersect them pairwise starting from the smallest, or keep a finger per array.
• The arrays live on two different machines and are huge? Stream both sorted files and merge them the same way, using almost no memory.

Remember this

Grown-up words: the fingers are two pointers, the walk is the merge step of merge sort, the "all" list is the set union and the "both" list is the set intersection.