I'm looking to learn more about algorithms and how to think like a programmer, by practicing coding problems. I subscribed to the mailinglist of dailycodingproblem.com so I will receive one such problem in my inbox every morning and see if I can solve it before the end of the day. Learn with me!

This problem was asked by Stripe.

Problem:


Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.

My thought process:

  • First thought: I could instigate a loop running from 1 to infinity and check for each number if it's present in the array with the indexOf() method.
  • But that is not very efficiënt. After all, if you'd have an array with 100 elements from 1 to 100, you would go over all 100 elements 100 times, so ten thousand steps, before you'd find out that the correct answer was 101.
  • Second thought, if there is an efficient way to reorganize the array in ascending order, only one loop would be required. We can actually use the sort() method to sort the array of numbers in ascending order. Default behavior here is alphabetical order, but we can achieve ascending order if we a provide a compareFunction as an argument. This compareFunction itself will take two arguments, namely the first and second element for comparison.

Solutions:

Firstly, the simple, inefficient solution just using the indexOf() method in a while loop. Seeing how the number of operations would increase exponentially with the number of inputs, this is a O(n^2) quadratic time solution.


function justLoop(arr){
  let i = 1
  while (arr.indexOf(i) !== -1){
    i++
  }
  return i
}

Secondly, a solution that is more efficient with larger data sets. I first reorganize the array in ascending order with sort(), and then loop over once. Seeing how this requires only two loops, regardless of the number of inputs, the time complexity of this solution is O(n) linear time, which is vastly better.


function findLowestInt(arr){
  arr.sort((a,b) => a-b);
  let min = 1
  for(let i = 0; i < arr.length+1; i++){
      if(arr[i] === min) min++
  }
  return min++
}

Do you have an even better solution? Let me know!