Common Elements in Three Sorted Arrays

Easy
617.

Common Elements in Three Sorted Arrays

Common Elements in Three Sorted Arrays is an easy coding problem on arrays and two pointers, asked in Amazon, Infosys and Oracle interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} a
 * @param {number[]} b
 * @param {number[]} c
 * @return {number[]}
 */
var commonElements = function(a, b, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Common Elements in Three Sorted Arrays — Problem & Solution

Common Elements in Three Sorted Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Common Elements in Three Sorted Arrays is an easy coding problem on arrays and two pointers, asked in Amazon, Infosys and Oracle interviews.

  • Difficulty: Easy
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, Infosys, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Common Elements in Three Sorted Arrays

  1. Hint 1

    Three pointers, one per array, all starting at 0.

  2. Hint 2

    If all three point at the same value, record it and advance all three.

  3. Hint 3

    Otherwise advance whichever pointer sits on the smallest value — it can never match anything later.

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

Java

public static int[] 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) {
        if (a[i] == b[j] && b[j] == c[k]) {
            if (out.isEmpty() || out.get(out.size() - 1) != a[i]) out.add(a[i]);
            i++; j++; k++;
        } else if (a[i] < b[j]) i++;
        else if (b[j] < c[k]) j++;
        else k++;
    }
    int[] res = new int[out.size()];
    for (int t = 0; t < out.size(); t++) res[t] = out.get(t);
    return res;
}

C++

vector<int> commonElements(vector<int>& a, vector<int>& b, vector<int>& c) {
    vector<int> out;
    size_t i = 0, j = 0, k = 0;
    while (i < a.size() && j < b.size() && k < c.size()) {
        if (a[i] == b[j] && b[j] == c[k]) {
            if (out.empty() || out.back() != a[i]) out.push_back(a[i]);
            i++; j++; k++;
        } else if (a[i] < b[j]) i++;
        else if (b[j] < c[k]) j++;
        else k++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique