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.


Tech mentioned