A Faster Approach, But Harder to Grok

In the above solution, the runtime complexity appears to be O(n^2) because of the additional while loop-- but it isn't too hard to show that we never iterate through more than n elements. This is still O(n) linear time because regardless of whether we enter the while clause, we'll still be iterating through the same number of input.

However, we can still speed this up by iterating through both the input array and the "comparison array" simultaneously.

xxxxxxxxxx

function missingNumber(input) {

  let result = [];

​

  for (

    let i = 0, targetValue = input[0];

    targetValue <= input[input.length - 1];

    targetValue++

  ) {

    if (input[i] != targetValue) {

      result.push(targetValue);

    } else {

      i++;

    }

  }

​

  return result;

}