Union and Intersection of two sorted arrays

Easy

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":[]}

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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 };
}