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