Find The Smallest Positive Integer Not Occurring In An Array - 3 Approaches

TIL: For certain reasons 🥁 I did a coding challenge on Codility for once and now I want to share my approaches with you.

Table of contents

1. Task
2. Approach 1: For-Loop
3. Approach 2: Map-Function
4. Approach 3: Set

---

Task

Write a function: function solution(A); that, given an array A of $\mathbb{N}$ integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

$\mathbb{N}$ is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].

Approach 1: For-Loop

For the first solution we are going to use the for loop.

Step 1: First, we filter the array (which returns a new array) to only get the positive integers, because when only negative integers are in the array, the answer should always return 1.

Step 2: Then we sort the new array in an ascending order.

Step 3: Now, let's create a variable called x, which stores 1 as a value, because of the reason mentioned before (the smallest possible return is 1).

Step 4: Create the for loop. The for-loop checks if the number in the array is bigger then x, and when it is, then we already have the solution 1.

Step 5: Otherwise, let's update x by the number with which it was compared to increased by 1.

Step 6: When the for-loop is finished, return x.

function solution(A) {
  const pos = A.filter(num => num >= 1).sort((a, b) => a - b);
  let x = 1;

  for(let i = 0; i < pos.length; i++) {
    if (x < pos[i]) {
      return x;
    }
    x = pos[i] + 1;
  } 
  return x;
}

console.log(`The solution is ${solution([1, 3, 8, 4, 1, 2])}`);

Approach 2: Map-Function

For the second solution we are going to use the map function.

Step 1: We create a variable called x like we did in Approach 1 Step 3.

Step 2: We use filter() like we did in Approach 1 Step 1.

Step 3: Then let's usesort() like we did in Approach 1 Step 2.

Step 4: Now we are going to use map(). map() also creates a new array calling a provided function on every element in the array.

Step 5: Within map() we again check if xis smaller then the current number in the array and return it. (Shortcut: If return is in the same line the if statement, there is no need for {} and it will return x.)

Step 6: Otherwise x will be updated by the number with which it was compared to increased by 1.

Step 7: When the functionality x is returnd.

function solution(A) {
    let x = 1

    A.filter(x => x >= 1)
     .sort((a, b) => a - b)
     .map((val, i, arr) => {
        if(x < arr[i]) return 
        x = arr[i] + 1
    })
    return x
}

console.log(`The solution is ${solution2([-1, 3, 8, 6, 1, 2])}`);

Approach 3: Set

For the last solution we are going to use set() method.

Step 1: Create a variable called set, and store a new instance of Set() with the array.

Step 2: Once again, let's create a variable called x, which stores 1 as a value, because of the reason mentioned before (the smallest possible return is 1).

Step 3: We are using the while loop which loops over the set and looks if set has i in it. While this is the case, i will be incremented by 1 until the value of i is not in the set, then i will be returned.

function solution(A) {
  const set = new Set(A);
  let i = 1;

  while (set.has(i)) {
    i++;
  }
  return i;
}

console.log(`The solution is ${solution3([1, 8, 6, 1, 2])}`);

Find here the Link To The Pen on CodePen.

---

Thanks for your reading and time. I really appreciate it!

Comments

[Michael]

Hello! I made an account just to ask this. What is happening in the filter line of the for loop solution? I have never seen a double implementation of the arrow function like that. What is it doing/yielding? Thank you!

[Julia 👩🏻‍💻 GDE]

Hey Michael. I am not quite sure if I understand your question right.

As described in Step 4: The for-loop checks if the number in the array is bigger then x, and when it is, then we already have the solution 1.

[Michael]

Apologies. I only referenced the for loop so you knew which solution I was referring to. The line of code I am asking about is the filter, which is where the double arrow function is being used.

Thank you :)

[Julia 👩🏻‍💻 GDE]

I still don‘t understand to be honest 🙊 are you talking about this line of code, which is described in Step 1 and 2 of Approach 1: For loop?

const pos = A.filter(num => num >= 1).sort((a, b) => a - b);

[Michael]

I'm so sorry I'm not being clear enough! Yes, that is the line I'm referring to. I should have just copied and pasted it like you did. Right here I see two arrow functions being used back to back in a way I've never seen before, and do not understand what is happening there.
(num => num >= 1)

[Julia 👩🏻‍💻 GDE]

I see. :)

These are actually not two arrow functions. The first part num => means like take each number in the list, the second part num >= 1 is a comparison for each number in the list (like the action you want to do after you crabbed each number of the list) meaning for each num bigger or equal to 1 in this list.

Hopefully, everything is clear now. Please reach out to me any time if you have further questions.

[Michael]

Ha! Wow, I feel silly. Glad I asked though. Thank you for being patient with me, I thought I was witnessing some new sorcery. That makes perfect sense now.

[Julia 👩🏻‍💻 GDE]

Oh please, don‘t feel silly! We are here to learn and share 😊

[Michael]

Thank you for that. In the gaming community there is an acronym of RTFC, and I certainly failed to meet that standard here!

[Raí B. Toffoletto]

Nice solutions! The disadvantage of the map is that you need to wait the map() iterate on all itens in the array, whilst 1 and 3 you end the function as soon you find a valid value. Have you try to benchmark those approachs to see which one performs better?

[Julia 👩🏻‍💻 GDE]

Thanks for your your comment. Actually, I wanted to test all three of them on performance but I am still new to performance measuring. I am curious though. Hopefully I can add measurements to each solution soon.

[insidewhy]

I'd go with something like solution one but not bother to sort or filter the array first. Filtering alone is O(n) and you can easily get an O(n) solution without needing to filter, let alone sort.

[Julia 👩🏻‍💻 GDE]

Nice. Would you mind posting your solution here? I always try to make my coding tutorials as beginner friendly as possible, but it would be nice to add a more advanced solution as well!