Common Elements in Three Sorted Arrays — Easy Problem & Solution

Problem statement

Given three arrays a, b and c, each sorted in non-decreasing order, return the values that appear in all three.

The result must be sorted ascending and contain each value once, even if it repeats in the inputs. Return [] when nothing is common.

Example 1

Input: a = [1,5,10,20,40,80], b = [6,7,20,80,100], c = [3,4,15,20,30,70,80,120]
Output: [20,80]

Example 2

Input: a = [1,2,3], b = [4,5,6], c = [7,8,9]
Output: []

Example 3

Input: a = [1,1,2,2,3], b = [1,1,2,2,3], c = [1,2,2,3,3]
Output: [1,2,3]
Explanation: Duplicates collapse to one entry each.

Constraints

• 1 <= a.length, b.length, c.length <= 100000
• 1 <= values <= 1000000
• Each array is sorted non-decreasing.

How to solve Common Elements in Three Sorted Arrays

Sorted inputs make a three-way merge possible: keep one pointer per array and always move the one that is behind, because a value smaller than another array's current value can never appear there again.

Approach

1. Start i, j, k at 0 and loop while all three are in range.
2. If a[i] == b[j] == c[k], append the value unless it equals the last one recorded, then advance all three pointers.
3. Otherwise advance the pointer whose value is the smallest of the three.

Why it works

Each array is sorted, so if a[i] is strictly smallest it cannot equal anything at or after b[j] and c[k] — discarding it is safe. Every pointer only moves forward, so the scan is linear.

Complexity

• Time — O(n + m + p)
• Space — O(1) beyond the output

Pitfalls

• Forgetting the duplicate guard — [1,1] in all three arrays would report 1 twice.
• Advancing all three pointers on a partial match loses values.

Reference solution

Python

from typing import List

def commonElements(a: List[int], b: List[int], c: List[int]) -> List[int]:
    out = []
    i = j = k = 0
    while i < len(a) and j < len(b) and k < len(c):
        if a[i] == b[j] == c[k]:
            if not out or out[-1] != a[i]:
                out.append(a[i])
            i += 1
            j += 1
            k += 1
        elif a[i] < b[j]:
            i += 1
        elif b[j] < c[k]:
            j += 1
        else:
            k += 1
    return out

JavaScript

var commonElements = function(a, b, c) {
    var out = [];
    var i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length && k < c.length) {
        if (a[i] === b[j] && b[j] === c[k]) {
            if (out.length === 0 || out[out.length - 1] !== a[i]) out.push(a[i]);
            i++; j++; k++;
        } else if (a[i] < b[j]) i++;
        else if (b[j] < c[k]) j++;
        else k++;
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy