Good morning! Here's our prompt for today.

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?

1missingNumbers([1, 2, 4, 5, 7]);
2// [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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def missing_numbers(num_arr):

    missing = []

    # fill in

    return missing

​

​

import unittest

​

​

class Test(unittest.TestCase):

    def test_1(self):

        assert missing_numbers([0, 1, 3]) == [2]

        print("PASSED: missing_numbers([0, 1, 3]) should equal [2]")

​

    def test_2(self):

        assert missing_numbers([10, 11, 14, 17]) == [12, 13, 15, 16]

        print(

            "PASSED: missing_numbers([10, 11, 14, 17]) should equal [ 12, 13, 15, 16 ]"

        )

​

    def test_3(self):

        assert missing_numbers([3, 7, 9, 19]) == [

            4,

            5,

            6,

            8,

            10,

            11,

            12,

Here's a video of us explaining the solution.

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?

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.

xxxxxxxxxx

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.

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;

}