Find common elements In 3 sorted arrays

The problem, simply

You get three arrays. Each one is sorted from small to big. Find every number that is in all three arrays, and give them back in sorted order, each number once.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each number in A, look it up in B and in C. Because B and C are sorted, a lookup can use binary search: open the list in the middle, and throw away the half that is too big or too small.

1. For each number x in A (skip repeats).
2. Binary search for x in B and in C.
3. If both find it, add x.

class Solution {
    public List<Integer> commonElements(int[] a, int[] b, int[] c) {
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if (i > 0 && a[i] == a[i - 1]) continue;          // skip repeats in A
            if (Arrays.binarySearch(b, a[i]) >= 0 && Arrays.binarySearch(c, a[i]) >= 0) {
                out.add(a[i]);
            }
        }
        return out;
    }
}

How long it takes: for each of the n1 numbers in A, two binary searches, so O(n1 * (log n2 + log n3)). Extra room: O(1) besides the answer. This is actually a good choice when A is tiny and B and C are huge.

Way 2: the clever way

Put one finger on each list: i on A, j on B, k on C.

1. Look at the three numbers under the fingers.
2. If all three are equal, it is shared. Write it down (unless it was the last thing written) and move all three fingers.
3. Otherwise, find the smallest of the three and move every finger that points at it. That number can never be shared.
4. Stop as soon as any finger falls off the end of its list.

class Solution {
    public List<Integer> commonElements(int[] a, int[] b, int[] c) {
        List<Integer> out = new ArrayList<>();
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length && k < c.length) {
            int small = Math.min(a[i], Math.min(b[j], c[k]));
            if (a[i] == small && b[j] == small && c[k] == small) {
                if (out.isEmpty() || out.get(out.size() - 1) != small) out.add(small);
                i++; j++; k++;                       // shared: move everyone
            } else {
                if (a[i] == small) i++;              // the smallest can never be shared
                if (b[j] == small) j++;
                if (c[k] == small) k++;
            }
        }
        return out;
    }
}

How long it takes: every step moves at least one finger forward, and no finger moves back, so at most n1 + n2 + n3 steps, O(n1 + n2 + n3). Extra room: three fingers, O(1).

Watch out for

• Stop when any list ends, not when all end.
• Moving a finger that is not on the smallest number skips a possible match.
• Repeated numbers: without the "last written" check, [2, 2] in all three lists gives [2, 2].

What interviewers ask next

• What about k sorted lists? Intersect them two at a time, smallest lists first, or keep a finger per list and always move the smallest one using a min heap. O(N log k) for N total numbers.
• What if the lists are not sorted? Count with a hash map: add each list's distinct numbers and keep those with count 3. O(n1 + n2 + n3) time, but O(n) extra room.
• What if one list is tiny and the others are huge? Use Way 1, binary searching the big lists, or gallop: jump 1, 2, 4, 8 places ahead to find the next candidate quickly.
• Keep repeats, like a multiset ([2, 2] shared twice)? Drop the "last written" check.

Remember this

Grown-up words: the fingers are pointers (three pointers), looking in the middle of a sorted list is binary search, and the shared numbers are the intersection of the three sets.