Find Missing Number in Array

We're given an array of continuous numbers that should increment sequentially by 1, which just means that we expect a sequence like:

[1, 2, 3, 4, 5, 6, 7]

However, we notice that there are some missing numbers in the sequence.

[1, 2, 4, 5, 7]

Can you write a method missingNumbers that takes an array of continuous numbers and returns the missing integers?

missingNumbers([1, 2, 4, 5, 7]);
// [3, 6]

Constraints

• Length of the array <= 100000
• The array will always contain non negative integers (including 0)
• Expected time complexity : O(n)
• Expected space complexity : O(1)

```js
function missingNumbers(numArr) {
	let missing = [];
	return missing;
}
```

The key thing to note here is that the numbers are sequential, and as such there's an expectation that the input array is sorted to begin with. In other words, since the numbers are incrementing by one at each index, they'll by definition be sorted in ascending order.

Knowing that, we can do a simple iteration through the array, and check that the difference between the current number and the one before it is 1.

The difficult part is when there are gaps larger than 1. For example:

[3, 4, 7, 8]

When we get to 7, we'll notice that the difference between it and the last number (4) is 3, which is more than just a gap of 1.

Knowing that, we can simply use a while loop to append the appropriate numbers in the missing array while keeping a counter. Let's call this counter diff. It'll track how many numbers we have to append before we close the gap.

```js
const numArr = [3, 4, 7, 8];

const missing = [];

for (let i in numArr) {
  // get the size of the gap
  let x = numArr[i] - numArr[i - 1];
  // start filling in the gap with `1`
  let diff = 1;
  // while there's still a gap, push the correct numbers
  // into `missing`, calculated by the number + diff
  while (diff < x) {
    missing.push(numArr[i - 1] + diff);
    diff++;
  }
}

console.log(missing);

```

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.

```js
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;
}

```

One Pager Cheat Sheet

• Write a function missingNumbers that takes an array of continuous numbers and returns the missing integers in O(n) time with O(1) space complexity.
• The key to finding the missing number in an array is to make sure that the array is sorted in ascending order, then check that each adjacent number is incrementing by 1, or use a while loop to append the appropriate numbers.
• This approach is harder to grok, however it can be optimized by iterating through both arrays simultaneously, resulting in an O(n) runtime complexity.