# Codility efficient algorithm solutions in JavaScript

Table of Contents

This post aim is to provide Codility algorithm solutions in JavaScript as there are so many of them 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.

I created this article to prepare for Toptal interview process. If you wish to apply to Toptal, here is a referral link that will link your account to mine if you are successful!

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; }

Pingback: FrontEnd courses list | webappexpress()

Pingback: Toptal interview process explained | Julien Renaux Blog()

Pingback: JavaScript background to have before any job interview with top companies | Julien Renaux Blog()