Common elements in three sorted arrays
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: []
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;}