architect + engineer
Public
Edited
Oct 17, 2022
2 stars
/**
* Returns a list of numbers which are contained in both lists.
*
* @param {Array.<Number>} listA First array of elements. Will be sorted during execution.
* @param {Array.<Number>} listB Second array of elements. Will be sorted during execution.
* @returns {Array.<Number>} Array of numbers which are contained in both lists. The items are sorted.
*/
function intersection(listA, listB) {
if (listA == null) throw `listA not defined`;
if (listB == null) throw `listB not defined`;
const n = listA.length;
const m = listB.length;
// sort both lists in-place
listA.sort(d3.ascending); // <= O(n log n)
listB.sort(d3.ascending); // <= O(m log m)
const result = [];
let i = 0; // to iterate over listA
let j = 0; // to iterate over listB
// iterate over each array only once
while (i < n && j < m) { // <= O(n + m)
if (listA[i] < listB[j]) {
for (const ai = listA[i++]; i < n && ai == listA[i]; i++); // shift i and skip duplicates
} else if (listA[i] > listB[j]) {
for (const bj = listB[j++]; j < m && bj == listB[j]; j++); // shift j and skip duplicates
} else { // listA[i] == listB[j] => item occurs in both lists
result.push(listA[i]);
for (const ai = listA[i++]; i < n && ai == listA[i]; i++); // shift i and skip duplicates
for (const bj = listB[j++]; j < m && bj == listB[j]; j++); // shift j and skip duplicates
}
}
return result;
}
check([1, 2, 3], [2, 4, 5])
check([1, 2, 3], [])
check([10, 1, 2, 3, 4, 5, 6], [2, 4, 5, 10, 8, 1])
check([10, 1, 2, 2, 2, 3, 4, 5, 6], [2, 4, 5, 2, 10, 8, 1])
check([10, -1, 2, 2, -2, 3, 4, -5, 6], [2, 4, 5, -2, 10, 8, 1])
check([], [])
throws(() => intersection(null, null))
throws(() => intersection(null, []))
throws(() => intersection([], null))
throws(() => intersection())
throws(() => intersection([]))
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
