Union and Intersection of two sorted arrays
Problem
Given two sorted arrays, return their union (every distinct value in either array) and their intersection (every distinct value in both), each in sorted order.
Example 1
Input: a = [1, 3, 4, 5, 7], b = [2, 3, 5, 6] Output: union = [1,2,3,4,5,6,7], intersection = [3, 5]
Also asked as: Find the Union and Intersection of the two sorted arrays
Test cases
Case 1
Input: [1,3,4,5,7], [2,3,5,6]
Expected: {"union":[1,2,3,4,5,6,7],"intersection":[3,5]}Case 2
Input: [1,2,2,3], [2,2,4]
Expected: {"union":[1,2,3,4],"intersection":[2]}Case 3
Input: [1,2], [3,4]
Expected: {"union":[1,2,3,4],"intersection":[]}Case 4
Input: [], [1,2]
Expected: {"union":[1,2],"intersection":[]}View solutionHide solution1 approach
1. Merge-style two pointers
Time O(n + m)Space O(n + m) output
Advance the pointer at the smaller value; equal values go to the intersection (and once to the union).
function unionIntersection(a, b) { let i = 0, j = 0; const uni = [], inter = []; const pushUni = (x) => { if (uni[uni.length - 1] !== x) uni.push(x); }; while (i < a.length && j < b.length) { if (a[i] < b[j]) pushUni(a[i++]); else if (a[i] > b[j]) pushUni(b[j++]); else { pushUni(a[i]); if (inter[inter.length - 1] !== a[i]) inter.push(a[i]); i++; j++; } } while (i < a.length) pushUni(a[i++]); while (j < b.length) pushUni(b[j++]); return { union: uni, intersection: inter };}