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.