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

## 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 use`sort()`

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 `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.

```
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!*

## Oldest comments (13)

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?

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.

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.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!

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!

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.

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 :)

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);`

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)`

I see. :)

These are actually not

twoarrow functions. The first part`num =>`

means liketake 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) meaningfor 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.

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.

Oh please, donβt feel silly! We are here to learn and share π

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