Find The Smallest Positive Integer Not Occurring In An Array - 3 Approaches
Tags: javascript, computerscience, leetcode
Published: 2022-11-20 15:32:40

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](#chapter-1)
2. [Approach 1: For-Loop](#chapter-2)
3. [Approach 2: Map-Function](#chapter-3)
4. [Approach 3: Set](#chapter-4)

---

## Task<a name="chapter-1"></a>

Write a function: `function solution(A);` that, given an array `A` of {% katex inline %}\mathbb{N}{% endkatex %} 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:

{% katex inline %}
\mathbb{N}
{% endkatex %} 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<a name="chapter-2"></a>

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

**Step 1:**<a name="step-2"></a> 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:**<a name="step-3"></a> Then we sort the new array in an ascending order.

**Step 3:**<a name="step-1"></a> 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`.

```javascript
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<a name="chapter-3"></a>

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-1).

**Step 2:** We use `filter()` like we did in [Approach 1 Step 1](#step-2).

**Step 3:** Then let's use`sort()` like we did in [Approach 1 Step 2](#step-3).

**Step 4:** Now we are going to use [`map()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/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 `x`is 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.

```javascript
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<a name="chapter-4"></a>

For the last solution we are going to use [`set()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/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.

```javascript
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](https://codepen.io/YuriDevAT/pen/jOKLPOy?editors=0110).


---
![Thank you](https://docs.google.com/uc?export=download&id=166Ecq6uBl61U14OUlkHOHIBv2ArKoumJ)

_Thanks for your reading and time. I really appreciate it!_