Common Elements in Three Sorted Arrays

Common Elements in Three Sorted Arrays asks you to find the values that appear in all three arrays. Because the arrays are already sorted, you do not need any extra hashing — a single coordinated walk with three pointers solves it in linear time.

The slow way first

The blunt approach: dump each array into a hash set and intersect the three sets. That works and is O(n + m + p) time, but it throws away the gift the problem gave us — the arrays are already sorted — and it spends O(n) extra space on the sets.

The question to ask: if everything is sorted, can I just merge? Sorted order means the smallest unmatched value is always at one of my three cursors. So I can step through all three arrays together, the same way you merge during merge sort, and use O(1) extra space.

The idea: advance the smallest

Keep three pointers i, j, k, one per array, all starting at 0. Look at a[i], b[j], c[k]:

• If all three are equal, that value is common to all arrays — record it, then advance all three pointers past it.
• Otherwise, advance the pointer sitting on the smallest value. That value can never be the common one (something is bigger than it), so moving past it loses nothing.

Why advancing the smallest is safe: if a[i] is the smallest of the three, then b[j] and c[k] are both larger, so a[i] is missing from at least one of them. It can never be a common element, and since a is sorted, no later value in a will be smaller — so we will never need a[i] again.

Walk through it

Step through the animation. The three rows are a, b, c, each with its own pointer. On most steps the values differ and one pointer slides forward. Twice — at 2 and at 5 — all three cursors line up on the same value, we add it to result, and all three pointers jump ahead together. The walk stops the moment any one pointer runs off the end of its array.

Pseudocode

i = j = k = 0
result = empty list
while i, j, k are all in range:
    if a[i] == b[j] == c[k]:
        if result is empty or its last value != a[i]:
            append a[i] to result        # skip duplicates
        i += 1; j += 1; k += 1           # advance all three
    else advance the pointer on the smallest value:
        if a[i] is smallest: i += 1
        elif b[j] is smallest: j += 1
        else: k += 1
return result

The Python solution

def common(a, b, c):
    i = j = k = 0
    res = []
    while i < len(a) and j < len(b) and k < len(c):
        if a[i] == b[j] == c[k]:
            if not res or res[-1] != a[i]:
                res.append(a[i])
            i += 1; j += 1; k += 1
        elif a[i] <= b[j] and a[i] <= c[k]:
            i += 1
        elif b[j] <= c[k]:
            j += 1
        else:
            k += 1
    return res

• i, j, k start at 0 and only ever move forward — that is why the walk is linear.
• The while keeps going only while all three pointers are still in range; if any array is exhausted, no more common elements are possible.
• Line 5 is the hit: a[i] == b[j] == c[k] chains the comparison, so all three must match.
• Lines 6–7 skip duplicates — we append only if res is empty or its last value differs, so a repeated common value is recorded once.
• Line 8 advances all three past a matched value.
• The elif chain (lines 9–14) handles the no-match case by stepping the pointer on the smallest value forward.

Complexity

Each step advances at least one pointer, and no pointer ever moves backward, so the total work is bounded by the combined length of the three arrays. The big win over the hash approach is space: we use only a few integer pointers instead of building sets.

When this pattern shows up

Practice