Missing Numbers¶
JavaScript¶
Solution 1¶
/**
* Finds numbers that are present in `ys` but missing in `xs`.
*
* - T.C: O(n).
* - S.C: O(n).
*
* @param {number[]} xs
* @param {number[]} ys
* @returns {number[]} The array of the missing numbers (the
* difference).
*/
function missingNums(arr, brr) {
var freqXs = {},
freqYs = {},
i,
n;
for (i = 0; n = xs[i], i < xs.length; ++i)
freqXs[n] = freqXs[n] + 1 || 1;
for (i = 0; n = ys[i], i < ys.length; ++i)
freqYs[n] = freqYs[n] + 1 || 1;
return Object.keys(freqYs).reduce((missing, key) => {
if (freqYs[key] === freqXs[key])
return missing;
missing.push(Number(key));
return missing;
}, []);
}
Solution using frequency counters. There are three loops involved but neither is nested, which makes for time complexity \(O(n)\).
Solution 2 with helper¶
/**
* Returns a hash map of the frequencies of the values in `xs`.
*
* - T.C: O(n).
* - S.C: O(n).
*
* @param {number[]} xs
* @returns {{ [key: string]: number }}
*/
function countFreq(xs) {
return xs.reduce(function reducer(freqs, x) {
freqs[x] = freqs[x] + 1 || 1;
return freqs;
}, {});
}
/**
* Finds numbers that are present in `ys` but missing in `xs`.
*
* - T.C: O(n).
* - S.C: O(n).
*
* @param {number[]} xs
* @param {number[]} ys
* @returns {number[]} The array of the missing numbers (the
* difference).
*/
function missingNums(xs, ys) {
var freqXs = countFreq(xs);
var freqYs = countFreq(ys);
return Object.keys(freqYs).reduce((missing, key) => {
if (freqYs[key] === freqXs[key]) return missing;
return [...missing, Number(key)];
}, []);
}
Essentially the same as solution 1, but extracting part of the logic into a helper function.
Solution 3 with sets, spread, sort and splice¶
/**
* Compares two numbers for ascending sorting.
*
* - T.C: O(1).
* - S.C: O(1).
*
* @param {number} a
* @param {number} b
* @returns {number}
*/
function sortAsc(a, b) {
return a - b;
}
/**
* Finds numbers that are present in `ys` but missing in `xs`.
*
* - T.C: O(n²).
* - S.C: O(1).
*
* @param {number[]} xs
* @param {number[]} ys
* @returns {number[]} The array of the missing numbers (the
* difference).
*/
function missingNums(xs, ys) {
for (const n of xs) {
if (ys.includes(n)) {
const idx = ys.indexOf(n);
ys.splice(idx, 1);
}
}
//
// • Use sets to remove duplicates.
// • Convert back to array with spread syntax.
//
return [...new Set(ys)].sort(sortAsc);
}
For each number in xs
, try to find it in ys
and remove it from ys
if present.
In the end, only numbers in ys
that are missing in xs
will remain in ys
.
Also use some ECMAScript set and spread stuff to return the final result.