Good evening! Here's our prompt for today.

We have an unsorted array of integers such as the following:

1[0, 3, -1, -2, 1]

In the above example, the minimum number is -2 and the maximum is 3. If it were sorted, it would look like:

1[-2, -1, 0, 1, 3]

This means there is an expected range (defined as the collection of values between the minimum and maximum values) of [-2, -1, 0, 1, 2, 3] for the array.

But look at the example again:

1[-2, -1, 0, 1, 3]

We're missing a number: 2. The smallest missing positive integer for our input array is 2.

Can you write a method that takes such an array and returns the first missing positive integer?

1leastMissingPositive([1, 2, 3, 0])
2// 4

In the above example, it is 4 since we already have 0 through 3. Have your code run in O(n) time with constant space (hence, we can easily determine if it was sorted, but most sorts will take O(n * log n) time).

Constraints

• Length of the array <= 100000
• The array can be empty
• The array will contain values between -100000 and 100000
• The final answer will always fit in the integer range
• 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

  console.log('PASSED: ' + 'Expect `leastMissingPositive([])` to return `1`');

var assert = require('assert');

​

function leastMissingPositive(nums) {

  // return nums;

}

​

try {

  assert.equal(leastMissingPositive([3, 5, -1, 1]), 2);

​

  console.log(

    'PASSED: ' + 'Expect `leastMissingPositive([3,5,-1,1])` to return `2`'

  );

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(leastMissingPositive([5, 6, 7, 8, 9]), 1);

​

  console.log(

    'PASSED: ' + 'Expect `leastMissingPositive([5,6,7,8,9])` to return `1`'

  );

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(leastMissingPositive([]), 1);

​

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 how we would solve this problem...

How do I use this guide?