This post aim is to provide Codility algorithm solutions in JavaScript as there are so many of then available out there. I am not pretending to have the best algorithm possible but at least the following answers scored 100% on Codility test result.

After reading the task description a wise thing to do is to check the expected worst case time complexity. It gives you a hint on how to apprehend the solution. For instance if the worst case time complexity is O(N), you would probably need to use a for loop, if it is O(N*M) a nested for loop might be necessary etc.

This post in on going, I am adding new solutions often.

## Lesson 1: Time Complexity

### FrogJmp

Difficulty: PAINLESS

Count minimal number of jumps from position X to Y.

https://codility.com/demo/take-sample-test/frog_jmp

Expected time complexity: worst-case is O(1)

function solution(X, Y, D) {
return Math.ceil((Y - X)/ D);
}

### PermMissingElem

Difficulty: PAINLESS

Find the missing element in a given permutation.

https://codility.com/demo/take-sample-test/perm_missing_elem

Expected time complexity: worst-case is O(N)

function solution(A) {
var length = A.length;
var sum = ((length + 1) /2) * (length + 2);
var sumMinusMissing = 0;
for (i = 0; i < length; i++) {
sumMinusMissing += A[i];
}
return sum - sumMinusMissing;
}

### TapeEquilibrium

Difficulty: PAINLESSS

Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|

https://codility.com/demo/take-sample-test/tape_equilibrium

Expected time complexity: worst-case is O(N)

function solution(A) {
var sumAfter = sumBefore = 0;
var minDiff = Number.POSITIVE_INFINITY;
A.forEach(function(value){
sumAfter += value;
});
for (var i = 1; i < A.length; i++){
sumBefore += A[i -1];
sumAfter = sumAfter - A[i -1];
minDiffTemp = Math.abs(sumBefore - sumAfter);
if (minDiffTemp < minDiff){
minDiff = minDiffTemp;
}
}
return minDiff;
}

## Lesson 2: Counting Elements

### MaxCounters

Difficulty: RESPECTETABLE

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

https://codility.com/demo/take-sample-test/max_counters

Expected time complexity: worst-case is O(N+M)

function solution(N, A) {
var counters = [],
size = N,
max = 0,
forValue = 0,
counter = 0,
lastUpdate = 0;
// init zeros
for (var i = 0; i < N; i++){
counters[i] = 0;
}
for (var i = 0; i < A.length; i++){
if (A[i] <= N){
position = A[i] -1;
if (counters[position] < lastUpdate){
counters[position] = lastUpdate + 1;
} else {
counters[position] = counters[position]+1;
}
if (counters[position] > max) {
max = counters[position];
}
} else {
lastUpdate = max;
}
}
for (var i = 0; i < N; i++){
if (counters[i] < lastUpdate)
counters[i] = lastUpdate;
}
return counters;
}

### MissingInteger

Difficulty: RESPECTETABLE

Find the minimal positive integer not occurring in a given sequence.

https://codility.com/demo/take-sample-test/missing_integer

Expected time complexity: worst-case is O(N)

function solution(A) {
var onlyPositiveInt = [];
for (var i =0; i < A.length; i++){
if (A[i] > 0 ){
onlyPositiveInt[A[i]] = true;
}
}
for (i = 1; i <= onlyPositiveInt.length; i++){
if (!onlyPositiveInt[i]){
return i;
}
}
return 1;
}

## Lesson 3: Prefix Sums

In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers x0, x1, x2, … is a second sequence of numbers y0, y1, y2, …, the sums of prefixes (running totals) of the input sequence

http://en.wikipedia.org/wiki/Prefix_sum

Material https://codility.com/media/train/3-PrefixSums.pdf

### PassingCars

Difficulty: PAINLESS

Count the number of passing cars on the road.

https://codility.com/demo/take-sample-test/passing_cars

Expected time complexity: worst-case is O(N)

function solution(A) {
var ones = 0, passing = 0;
for(var i=A.length-1; i>=0; i--) {
if (A[i] === 0){
passing += ones;
if (passing > 1000000000){
return -1;
}
} else {
ones ++;
}
}
return passing;
}

### CountDiv

Difficulty: RESPECTETABLE

Compute number of integers divisible by k in range [a..b].

https://codility.com/demo/take-sample-test/count_div

For this one your coding skills won’t help. It is a pure math problem.

Expected time complexity: worst-case is O(1)

function solution(A, B, K) {
if (A % K === 0)
return Math.floor((B - A) / K + 1);
return Math.floor((B - (A - (A % K) )) / K)
}

### MinAvgTwoSlice

Difficulty: RESPECTETABLE

Find the minimal average of any slice containing at least two elements.

https://codility.com/demo/take-sample-test/min_avg_two_slice

Expected time complexity: worst-case is O(N)

Still searching for this one. If you have a 100% solution please share 🙂

### GenomicRangeQuery

Difficulty: RESPECTETABLE

Find the minimal nucleotide from a range of sequence DNA.

https://codility.com/demo/take-sample-test/genomic_range_query

Expected time complexity: worst-case is O(N+M)

function solution(S, P, Q) {
var positionOne,
positionTwo,
factorPerType = {
"A":1,
"C":2,
"G":3,
"T":4
},
prefix = [[0,0,0,0]],
Plen = P.length,
Slen = S.length,
result =[],
counterType = [0,0,0,0];
for(var i = 0; i<Slen; i++) {
counterType = counterType.concat(); // local copy
counterType[factorPerType[S[i]] -1]++;
prefix.push(counterType);
}
for(i=0; i<Plen; i++) {
positionOne = P[i] + 1;
positionTwo = Q[i]+ 1;
var finalCount =0;
for (j = 0; j < 4; j++){
finalCount = prefix[positionTwo][j] - prefix[positionOne -1][j];
if (finalCount > 0){
result.push(j + 1);
break;
}
}
}
return result;
}

## Lesson 4: Sorting

### MaxProductOfThree

Difficulty: PAINLESS

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

https://codility.com/demo/take-sample-test/max_product_of_three

Expected time complexity: worst-case is O(N*log(N))

function solution(A) {
var N = A.length;
// Sort ascending
A.sort(function(a, b){
return a - b;
});
// the max product of three elements is the product of the last three
// elements in the sorted array or the product of the first two elements
// and the last element if the first two elements are negatives.
return Math.max(A[0] * A[1] * A[N-1], A[N-3] * A[N-2] * A[N-1]);
}

### Distinct

Difficulty: PAINLESS

Compute number of distinct values in an array.

https://codility.com/demo/take-sample-test/distinct

Expected time complexity: worst-case is O(N*log(N))

function solution(A) {
var leng = A.length, counter = 0;
// Sort ascending
A.sort(function(a, b){
return a - b;
});
for (var i=1; i <= leng; i++){
if (A[i] != A[i - 1]){
counter++;
}
}
return counter;
}

### Triangle

Difficulty: PAINLESS

Determine whether a triangle can be built from a given set of edges.

https://codility.com/demo/take-sample-test/triangle

Expected time complexity: worst-case is O(N*log(N))

function solution(A) {
var len = A.length;
// Sort descending
A.sort(function(a, b){
return b - a;
});
for(var i=0; i<len - 2; i++) {
var P = i, Q= i+1, R= i+2;
var condition1 = A[P] + A[Q] > A[R];
var condition2 = A[Q] + A[R] > A[P];
var condition3 = A[R] + A[P] > A[Q];
if (condition1 && condition2 && condition3){
return 1;
}
}
return 0;
}

### NumberOfDiscIntersections

Difficulty: RESPECTETABLE

Compute intersections between sequence of discs.

https://codility.com/demo/take-sample-test/number_of_disc_intersections/

Expected worst-case time complexity is O(N*log(N));

function solution(A) {
var len = A.length,
tupples = [],
count =0;
for (var i=0; i < len; i++){
tupples.push([i - A[i], i + A[i]]);
}
// [[5,5], [0,4], [-4, 6]] => [[-4, 6], [0,4], [5,5]]
tupples.sort(function(a,b){
return a[0] - b[0];
});
for (var j=0; j < len; j++){
var tupple = tupples[j];
for (var k=j+1; k < len; k++){
var comparisonTupple = tupples[k];
if (comparisonTupple[0] <= tupple[1]){
count++;
if (count >10000000){
return -1;
}
} else {
break;
}
}
}
return count;
}

## Lesson 5: Stacks and Queues

### Brackets

Difficulty: PAINLESS

Determine whether given string of parentheses is properly nested.

https://codility.com/demo/take-sample-test/brackets/

Expected worst-case time complexity is O(N)

function solution(S) {
var len = S.length;
if (!len){
return 1;
}
var stack = [],
matches = {
"{" : "}",
"(" : ")",
"[" : "]"
};
for (i=0; i < len; i++){
var currentCharacter = S[i];
if (matches[currentCharacter]){
stack.push(currentCharacter);
} else {
if (!stack.length){
return 0;
}
var previousCharacter = stack.pop();
if (matches[previousCharacter] !== currentCharacter){
return 0;
}
}
}
return (stack.length)? 0 : 1;
}

### Nesting

Difficulty: PAINLESS

Determine whether given string of parentheses is properly nested.

https://codility.com/demo/take-sample-test/nesting/

Expected worst-case time complexity is O(N)

function solution(S) {
var len = S.length;
if (!len){
return 1;
}
var stack = [],
matches = {
"(" : ")"
};
for (i=0; i < len; i++){
var currentCharacter = S[i];
if (matches[currentCharacter]){
stack.push(currentCharacter);
} else {
if (!stack.length){
return 0;
}
var previousCharacter = stack.pop();
if (matches[previousCharacter] !== currentCharacter){
return 0;
}
}
}
return (stack.length)? 0 : 1;
}

### Fish

Difficulty: PAINLESS

N voracious fish are moving along a river. Calculate how many fish are alive.

https://codility.com/demo/take-sample-test/fish/

Expected worst-case time complexity is O(N)

function solution(A, B) {
var len = A.length,
count = parseInt(len),
stackDownstreamFishes = [];
for (var i = 0; i < len; i++){
var direction = B[i] ? 'downstream' : 'upstream';
if (direction === 'downstream'){
stackDownstreamFishes.push(A[i]);
} else {
// Going backward through all downstream fishes
for(var j= stackDownstreamFishes.length-1; j>=0; j--) {
var lastDownstreamFishSize = stackDownstreamFishes[j];
if (lastDownstreamFishSize > A[i]){
count--;
break;
} else if (lastDownstreamFishSize < A[i]){
count--;
stackDownstreamFishes.pop();
}
}
}
}
return count;
}

### StoneWall

Difficulty: PAINLESS

Cover “Manhattan skyline” using the minimum number of rectangles.

https://codility.com/demo/take-sample-test/stone_wall/

Expected worst-case time complexity is O(N)

function solution(H) {
var len = H.length,
stack = [H[0]],
result = 1;
if (!len) {
return 0;
}
for (var i = 1; i < len; i++) {
var currentHeight = H[i];
while (stack.length && stack[stack.length - 1] >= currentHeight) {
if (currentHeight == stack[stack.length - 1]) {
result--;
}
stack.pop();
}
stack.push(currentHeight);
result++;
}
return result;
}

I started with a backward for loop:

for (var j = stack.length - 1; j >= 0; j--) {
if (stack[j] < currentHeight) {
break;
}
if (stack[j] == currentHeight) {
result--;
}
stack.pop();
}

But a while loop is faster: https://jsperf.com/compare-while-loop-vs-for-loop/4

## Lesson 6: Leader

Material https://codility.com/media/train/6-Leader.pdf

### EquiLeader

Difficulty: PAINLESS

Find the index S such that the leaders of the sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

https://codility.com/demo/take-sample-test/equi_leader/

Expected worst-case time complexity is O(N)

function solution(A) {
var len = A.length,
i = 0,
j = 0,
k = 0,
size = 0,
indexCount = 0,
candidateCount = 0,
leader,
leaderCount = 0,
candidate = null;
// First find the leader within A
for (; i < len; i++) {
if (size === 0) {
size++;
candidate = A[i];
} else {
(candidate === A[i]) ? size++ : size--;
}
}
for (; j < len; j++) {
if (A[j] === candidate) {
candidateCount++;
}
}
if (candidateCount <= len / 2) { // Our candidate failed 🙁
return 0;
} else { // we have a winner!
leader = candidate;
leaderCount = candidateCount;
}
var leaderLeftCount = 0;
for (; k < len - 1; k++) {
var lenLeft = (k + 1);
var lenRight = len - lenLeft;
if (A[k] === leader) {
leaderCount--;
leaderLeftCount++;
}
if (leaderLeftCount > (lenLeft / 2) && leaderCount > (lenRight / 2)) {
indexCount++;
}
}
return indexCount;
}

### Dominator

Difficulty: PAINLESS

Find an index of an array such that its value occurs at more than half of indices in the array.

https://codility.com/demo/take-sample-test/dominator/

Expected worst-case time complexity is O(N)

function solution(A) {
var len = A.length,
i = 0,
j = 0,
leaderCount = 0,
latestIndex = -1,
size = 0,
candidate = null,
value = null;
for (; i < len; i++){
if (size === 0){
size++;
value = A[i];
} else {
value !== A[i] ? size-- : size++;
}
}
candidate = value;
for (; j < len; j++){
if (candidate === A[j]){
leaderCount++;
}
if (leaderCount > len / 2){
latestIndex = j;
break;
}
}
return latestIndex;
}

## Lesson 7: Maximum slice problem

Material

### MaxProfit

Difficulty: PAINLESS

Given a log of stock prices compute the maximum possible earning.

Expected worst-case time complexity is O(N)

At first I could not find a better solution the following:

function solution(A) {
var len = A.length,
i= len-1,
max = 0;
for(; i>=0; i--) {
var stockShare = A[i];
for(j = i-1; j>=0; j--) {
var diff = stockShare - A[j];
if (diff > max){
max = diff;
}
}
}
return max;
}

The time complexity is quadratic O(N^2) which is terrible.

Then I spent a little more time thinking about it and I ended up writing the following which has the correct time complexity: O(N).