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.

Answer 3

How about

Javascript

function solution(A) {
    var minpos = 0,
        minavg = (A[0] + A[1]) / 2,
        N = A.length,
        N1 = N - 1,
        N2 = N - 2,
        sumTwo,
        t,
        i;

    for (i = 0; i < N2; i += 1) {
        sumTwo = A[i] + A[i + 1];
        t = sumTwo / 2;
        if (minavg > t) {
            minavg = t;
            minpos = i;
        }

        t = (sumTwo + A[i + 2]) / 3;
        if (minavg > t) {
            minavg = t;
            minpos = i;
        }

    }

    t = (A[N2] + A[N1]) / 2;
    if (minavg > t) {
        minavg = t;
        minpos = N2;
    }

    return minpos;
}

var A = [4, 2, 2, 5, 1, 5, 8];

console.log(solution(A));

On jsFiddle

Answer 4

Although Sheng's correction does help, the algorithm still does not work in all cases. For instance, the algorithm returns 2 for [-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]. Expected value is 0.

Possible Cause:

Consider an intermediate step of the algorithm. If A[i..j] has minimum average for slices starting with i, then to include element at i-1, only these options are considered:

• A[i-1...j]
• A[i-1...i]

Unfortunately, there could exist an index k such that avg(A[i...k]) > avg(A[i...j]), but avg(A[i-1...k]) < avg(A[i-1...j]). Although this can be proven mathematically, a single example should suffice here.

[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87] avg([65, -11, 73, -22]) = 26.25 avg([65, -11]) = 27 // This is ignored as avg is higher

In order to include -18, the algorithm considers [-18, 65, -11, 73, -22] and [-18, 65].

avg([-18, 65, -11, 73, -22]) = 17.4 avg([-18, 65]) = 23.5 avg([-18, 65, -11]) = 12 // True minimum which is not considered

I had submitted a similar solution and it scored 100% in Codelity. However, it isn't the correct solution.

Answer 5

In the other post I provide an extensive description of my solution. I'm not including it here because you already have the idea.

int solution(vector<int> &A) {

    // Find prefix sum.
    int N = A.size();
    vector<int> ps(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        ps[i] = A[i - 1] + ps[i - 1];
    }

    int lft_idx, min_lft_idx;
    double avg_here, min_avg, avg_of_two, avg_with_prev;

    // Initialize variables at the first possible slice (A[0:1]).
    lft_idx = min_lft_idx = 0;
    avg_here = min_avg = (A[0] + A[1]) / 2.0;

    // Find min average of every slice that ends at ith element,
    // starting at i = 2.
    for (int i = 2; i < N; i ++) {

        // average of A[lft_idx : i]
        avg_with_prev = ((double) ps[i + 1] - ps[lft_idx]) / 
                        (i - lft_idx + 1);

        // average of A[i - 1 : i]
        avg_of_two = (A[i - 1] + A[i]) / 2.0;

        // Find minimum and update lft_idx of slice
        // (previous lft_idx or i - 1).
        if (avg_of_two < avg_with_prev) {
            avg_here = avg_of_two;
            lft_idx = i - 1;
        }
        else
            avg_here = avg_with_prev;

        // Keep track of minimum so far and its left index.
        if (avg_here < min_avg) {
            min_avg = avg_here;
            min_lft_idx = lft_idx;
        }
    }

    return min_lft_idx;
}

It achieved 100% on Codility, and also gives the right answer to the example of @Manas Chaudhari.