First Missing Positive Number in an Array

I was recently asked in a Technical Interview to solve the following problem:

“Write a function to find the smallest non-negative integer that is not present in a given array of non-negative, distinct integers”

I thought this was an excellent question, because at first it seems very simple, but as you dig deeper into it, there will almost certainly be many ways to improve the initial solution you come up with. Let’s dive into it now.

Brute Force

When I’m doing these kind of questions (especially in an interview setting when the person interviewing you is watching you code, and there is a time component) I like to start by just getting something on the screen, and getting an answer.

The best way to do this is to come up with the brute force solution and then to optimize it once you have a working function, and can dive deeper into the logic.

In our case, the simplest brute force solution is nested for loops. The outer loop will count up from 0 (since 0 is the smallest non-negative integer) and will count all the way up until we find the number we are looking for.

The inner loop, will scan through the whole array looking for whatever number the outer loop gives it. If that number is found it will continue, and if not, we have our number and it will return it.

Let put that into practice:

const smallest = function(nums){
  for (let i = 0; i<Infinity; i++){
    if (!nums.includes(i)) return i
  }
  return nums.length
}

Simple and effective. This will look through all the numbers forever up until Infinity until we find a number not in the array. The .includes() method handles the inner loop for us.

Right now our Space Complexity is great O(1) but our Time Complexity is not the best O(N²)

Sorting

My next intuition was realizing that if we sorted the array, we could theoretically cut down the run time a lot since we then would only at most have to go through the array one time, just checking if the integers are in perfect order. In worst case scenario, we get all the way to the end of the array without finding a gap and we know the next smallest number is just the length of the array (for example in an array of [0,1,2,3] the smallest number not present would be 4 which is also the array’s length).

The code for that is as follows:

const smallest = function(nums){
  nums = nums.sort()
  
  if (nums[0] !== 0) return 0
  
  for(let i = 0; i< nums.length; i++){
     if (nums[i+1] - nums[i] !== 1){
       return nums[i] + 1
     }
   }
  return nums.length
}

Our For loop now only runs once for each element of the array so it is O(N). However, since our .sort() method runs in O(N log N) time complexity, it actually is the larger factor as compared to our linear loop. So our Time Complexity of O(N log N + N) reduces down to (O N log N).

Ok we’re getting closer, but we can do better.

Hash Table

My next intuition was then to use a hash table. Using a hash table trades memory for added speed, which is normally a tradeoff we’ll take.

const smallest = function(nums){
  hash = {}
  nums.forEach(num => {
    hash[num] = true
  })
for (let i =0; i<nums.length+1; i++){
    if (!hash[i]) return i 
  }
  return nums.length
}

You’ll start to see a pattern here where if we make it through all of our code that mean the smallest number not in the array is the length of the array, meaning the array included all of the number from 0 up to its size.

Our first loop goes through the array and creates a key value pair for each number in the array and stores it in the hash.

Then, our second loop iterates from 0 up to the length of the array checking if each number has a corresponding key in hash. If it doesn’t we break the loop and return the number.

There are two loops, but since they are not nested, you add their runtimes together instead of multiplying which gives us a Time Complexity of O(N + N) or O(2N) which we can reduct to O(N) and call linear. However, our Space Complexity is now O(N) instead of constant since we are using the hash.

This is as far as I was able to get during my interview, but I was given 2 major clues by my interviewer and told to keep working on a solution. Those 2 clues were:

1. Remember the inputs are UNIQUE and NON-NEGATIVE
2. The worst case scenario for number of iterations through the array occurs when every number from 0 to size is present, so the max iterations is N

Linear Time and Constant Space Solution

After racking my brain for a few hours, and finally stepping away, the solution finally came to me.

Since these numbers are all positive (or zero) we can take advantage of that fact by creating a sort of “in-place checklist” that will be able to keep track of numbers in linear time, without creating a new array.

We can accomplish this by using the value of each number, to “cross off” that number at its corresponding index. What does this mean? I’ll explain:

Let’s use the array [3,1,5,2,0] for our example.

When we get to array[0] the value is 3. We now know 3 is present. We can modify our array to “cross off” 3 and mark its presence by going to array[3] and turning the number there negative.

Our array will now be [3,1,5,-2, 0]

We will continue with this pattern until we reach the end of the array. In our case, our final array will look like [-3,-1,-5,-2, 0]

Now we can loop through and see which number’s are not negative. If they all are, we will know all the numbers are present, but if not, the index of the first one we run into will be the number we are looking for.

Now you may have noticed one issue in our example. The answer we are looking for is 4, because thats the smallest non-negative number. But in our array[4] the vale is neither negative or positive. It is zero. So we will have to write a special case to handle this situation in our code.

Let’s see it below:

cosnt smallest = function(nums) {
  let len = nums.length
    for (let i=0; i<len; i++){
      let idx = Math.abs(nums[i])
    if (nums[idx] === undefined){
      nums[idx] = 1
    }
    if (nums[idx] === 0){
      nums[0] *= -1
      nums[idx] = -1
    } else {
      nums[idx] *= -1
    }
  }
  
  for (let i=0; i<nums.length; i++){
    if (nums[i] > 0 ) return i
  }
  return nums.length
};

Now there are a couple of edge cased we handle in here. First, is the one I mentioned where we have a 0 in our array. We can’t multiply it by -1 like all of the other numbers, because it would remain zero. We also can’t adjust our if statement to say if nums[i] > 0 return i because there are cases where the index of 0 could have been counted, or it may not have been. We have no way of knowing.

We had to get creative and say, if we get to a number whose value is 0, then go to index 0, multiply that by -1, and THEN chance the 0 to a negative one. That way we don’t change the 0 to a negative number before get to it and ruin the ability to “cross off” the number at index 0.

Also, you’ll see that we create a variable ‘len’ at the beginning of our array. This is because sometimes if larger numbers are in our array, the way our function is set up, we store num[idx] to 1 when its undefined. for example if our array is [1, 2, 50, 3]. When we get to index 3 with a value of 50, we know that index 50 doesn’t exist for us to make a negative, so we set array[50] to 1 first and then make it negative, accounting for it in the array. Since this causes our array to grow, if we used nums.length in our for loop, we would run it way more times than we wanted to, and would be iterating over a bunch of blank spaces. Setting len to equal our original array length fixes this problem.

Finally, in our else condition, we need to account for the case where we changed our 0 to a -1 already, but it hasn’t been visited by our for loop. If this happens, we could accidentally change the number at index 1 back positive when it was already changed to negative.

This bit of code fixes that by making sure the number is positive before changing it to negative:

} else {
  if (nums[idx] > 0){
    nums[idx] *= -1
  }
}

Our final code looks like this:

cosnt smallest = function(nums) {
  let len = nums.length
    for (let i=0; i<len; i++){
      let idx = Math.abs(nums[i])
    if (nums[idx] === undefined){
      nums[idx] = 1
    }
    if (nums[idx] === 0){
      nums[0] *= -1
      nums[idx] = -1
    } else {
      if (nums[idx] > 0){
        nums[idx] *= -1
      }
    }
  }
  
  for (let i=0; i<nums.length; i++){
    if (nums[i] > 0 ) return i
  }
  return nums.length
};

And that’s it for today. Feel free to try the solution out for yourself and see if you can find any edge cases.