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.

big_o

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 &amp;&amp; condition2 &amp;&amp; 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 &amp;&amp; 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) &amp;&amp; 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).