Common elements in three sorted arrays

Easy

Problem

Given three arrays sorted in ascending order, return the distinct values that appear in all three, in sorted order.

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]

Also asked as: find common elements In 3 sorted arrays

Test cases

Case 1

Input:    [1,5,10,20,40,80], [6,7,20,80,100], [3,4,15,20,30,70,80,120]
Expected: [20,80]

Case 2

Input:    [1,1,2,2], [1,2,2], [1,2,2,3]
Expected: [1,2]

Case 3

Input:    [1,2], [3,4], [5,6]
Expected: []

Case 4

Input:    [], [1], [1]
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Three pointers

Time O(n1 + n2 + n3)Space O(1)

If all three current values are equal, record it; otherwise advance the pointer with the smallest value.

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