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!