Codility - min average slice

Question

I'm trying to find a solution to a codility question on minimum slice of a subarray, and I've devised a solution using a modified version of Kadane's algorithm. I've currently gotten 90/100 and managed to pass almost all the tests in O(n). However, I can't seem to pass "medium_range, increasing, decreasing (legth = ~100) and small functional, got 5 expected 3", and I have no idea why. This is possibly a repeat of solution, but I'm using a slightly different way of solving.

My logic is as follows:

a) if we have an array MinA where MinA[k] represents the minimum average slice of a subarray starting from k with minimum length of 2

b) then if we loop through MinA and find the minimum of the array, then this will be the minimum average slice for the whole array (and then return the index position)

c) to create this MinA, we start from the second last element of the array and MinA[A.length -2] is the average of the last two elements of A

d) we move the counter one position to the left; MinA[counter] will have to be either average of A[counter] and A[counter + 1] or the average of the elements counter and the elements in MinA[counter + 1]

e) if d was not true, then this implies that MinA[counter + 1] is not the minimal average slice from counter + 1 to some element from counter + 2 to N

I wonder if I'm missing something?

/*
 * Using modified version of Kadane's algorithm
 * The key logic is that for an array A of length N, 
 * if M[k + 1] is the minimum slice of a subarray from k + 1 to any element
 * between k+2 to n, then M[k] is either the average of A[k] and A[k + 1], or
 * the average of the elements k and the elements in M[k + 1]
 */
function solution(A) {
    // you can use console.log for debugging purposes, i.e.
    // console.log('this is debug message');
    // write your code in JavaScript (ECMA-262, 5th edition)
    var minSliceArray = [],
        counter = A.length - 2,
        currMinSliceLength = 0,
        min = Number.POSITIVE_INFINITY,
        minIndex = -1;

    minSliceArray[counter] = (A[counter] + A[counter + 1]) / 2;
    currMinSliceLength = 2;
    counter--;

    while (counter >= 0) {
        var a = (A[counter] + A[counter + 1]) / 2,
            b = (A[counter] + minSliceArray[counter + 1] * currMinSliceLength) / (currMinSliceLength + 1) ;
        if (a < b) {
            minSliceArray[counter] = a;
            currMinSliceLength = 2;
        } else {
            minSliceArray[counter] = b;
            currMinSliceLength++;
        }
        counter--;
    }

    //loops through the minSliceArray and find the minimum slice
    for (var i = 0; i < minSliceArray.length; i++) {
        if (minSliceArray[i] < min) {
            min = minSliceArray[i];
            minIndex = i;
        }
    }
    return minIndex;
}

Answer 1

To fix your problem, you could replace the code

if (a < b) {

with

if (a <= b) {

For example A = [-3, 3, -3, 3, -3], firstly, we are considering the A[3:5], and the average is 0. Then, we come to position 2, A[2:5]/3 = -1, and A[2:4]/2 = 0. So we choose the former. For position 1, A[1:3]/2 == A[1:5]/4 == 0. In OLD answer, we should continue to choose A[1:5]. Finally for position 0, we have A[0:2]/2 = 0, and A[0:5]/5 = -0.6 And we choose the later. After all, the overall minimual average is at position 3 as A[3:5]/3=-1. BUT actually A[0:3]/3 == -1 == A[3:5]/3.

Because of such traps, I did not use the modified version of Kadane's algorithm in my blog. But it should work well.

Answer 2

On the first attempt of this, I had a O(2^NN) algorithm, that was easy but got only 40% correctness and 0% performance:

function solution(A) {
    var m = null, c, n
    for ( var i = 0; i < A.length; ++i ) {
        for ( var j = i + 1; j <= A.length; ++j ) {
            c = A.slice(i, j + 1).reduce(function (a,b) { return a+b }) / (j - i + 1)
            if ( m === null || c < m ) {
                m = c
                n = i
            }
            else if ( c == m && i < n ) {
                n = i
            }
        }
    }
    return n
}

Slept on it and came up with this for the second attempt, got a O(N) algorithm, that got 100% correctness and 100% performance:

function solution(A) {
    if ( A.length < 2 )  return -1
    var result = A.reduce(function (a, b, bIndex) {
        var f = typeof a === 'number'
        var x, y, z
        z = {
            index: bIndex,
            value: b,
            couple: {
                start: bIndex - 1,
                sum:   x = (f ? a : a.value) + b,
                count: 2,
                avg:   x / 2
            },
            streak: {
                start: a.bestStreak ? a.bestStreak.start : 0,
                sum:   x = (f ? a : a.bestStreak.sum) + b,
                count: y = (f ? 1 : a.bestStreak.count) + 1,
                avg:   x / y
            }
        }

        z.bestStreak = z.couple.avg < z.streak.avg
            ? z.couple
            : z.streak

        z.best = !a.best || z.bestStreak.avg < a.best.avg
            ? z.bestStreak
            : a.best

        // console.log(JSON.stringify({z}, null, '  '))

        return z
    })
    return result.best.start
}

After solving it, I looked around to see how others have done it. IMHO my above solution is the easiest to understand and debug.

It works by knowing that no streak's average can become lower, if that streak does not contain a lower streak within itself.

This may seem odd, as you may be like - well what happens if I have an average streak, and then a super low number. Well the highest number in that streak is never the last number, as that would increase the average of the streak, breaking it. So the last number, is either a number beneficial to a streak, in which case the next number may be beneficial too, and may form a couple that is a better streak, or the last or current number are streak breakers and can be discarded.