AlgoDaily 17: Find Missing Number in Array
https://algodaily.com/challenges/find-missing-number-in-array
Seems like we should iterate on the array, adding an integer to the result array
if it’s not present in the input. We have to backtrack the iteration by one each
time we hit a missing number. This is O(n).
function missingNumbers(sequence) {
const missing = [];
let expected;
for (let i = 0; i < sequence.length; i++) {
if (i === 0) {
expected = sequence[i] + 1;
continue;
}
if (sequence[i] !== expected) {
missing.push(expected);
i--;
}
expected += 1;
}
return missing;
}
The solution suggested by Algo Daily is similar, but uses an inner loop to insert all of the missing numbers in a gap at once, rather than doing them one iteration at a time as in the solution above. This avoids the need to backtrack.