minimum slice position - Order N algorithm

Question

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.

Assume that:

N is an integer within the range [2..100,000]; each element of array A is an integer within the range [−10,000..10,000]. Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Can you post only solutions with order N only?

Answer 1

If A had only positive numbers, you could get away with this:

pos = 0
min_avg = A[0] + A[1]
for (i=2; i<N; i++)
    m = A[i-1] + A[i]
    if (m < min_avg)
        min_avg = m
        pos = i-1
return pos

This is only taking an average of a slice of two numbers, because a larger slice cannot have a smaller average than the minimum of a smaller slice.

If A has negative numbers, you could adjust all values upwards first:

offset = min(A)
for (i=0; i<N; i++)
    A[i] -= offset

Combined with the previous algorithm:

offset = min(A) * 2              (because we're adding two numbers below)
pos = 0
min_avg = A[0] + A[1] - offset
for (i=2; i<N; i++)
    m = A[i-1] + A[i] - offset
    if (m < min_avg)
        min_avg = m
        pos = i-1
return pos

Answer 2

I think you're right, the best I can do is an O(N²) solution (this is in Python):

from random import randint

N = 1000
A = [randint(-10000, 10000) for _ in xrange(N)]

def solution(A, N):
    min_avg = 10001
    for p in xrange(N):
        s = A[p]
        for q in xrange(1,N-p):
            s += A[p+q]
            a = s / (q+1.)
            if a < min_avg:
                min_avg = a
                pos = (p, q+1)
    return pos

print solution(A, N)

However, averages of larger slices tend towards the mean (middle) value of the original range. In this case, the average is zero, halfway between -10000 and 10000. Most of the time, the smallest average is of a slice of two values, but sometimes it can be a slice of three values and rarely it can be even more values. So I think my previous answer works in most (>90%) of the cases. It really depends on the data values.

Answer 3

    #include <assert.h>
    struct Slice { unsigned P, Q; };
    struct Slice MinSlice( int A[], unsigned N ) {
        assert( N>=2 );
        // find min slice of length 2
        unsigned P = 0;
        double min_sum = A[P] + A[P+1];
        for (unsigned i = 1; i < N-1; ++i)
            if ( min_sum > A[i] +A[i+1] ) {
                P = i;
                min_sum = A[P] + A[P+1];
            }
        unsigned Q = P+1;
        double min_avg = min_sum / 2;
        //extend the min slice if the avg can be reduced.
        //(in the direction that most reduces the avg)
        for (;;) {
            if ( P > 0 && ( Q >= N-1 || A[P-1] <= A[Q+1] ) ) {
                //reducing P might give the best reduction in avg
                double new_sum = A[P-1] + min_sum;
                double new_avg = new_sum / (Q - P + 2);
                if ( min_avg < new_avg )
                    break;
                min_sum = new_sum; 
                min_avg = new_avg; 
                --P;
             } else if ( Q < N-1 && ( P <= 0 || A[P-1] >= A[Q+1] ) ) {
                //increasing Q might give the best reduction in avg
                double new_sum = min_sum + A[Q+1];
                double new_avg = new_sum / (Q - P + 2);
                if ( min_avg < new_avg )
                    break;
                min_sum = new_sum; 
                min_avg = new_avg; 
                ++Q;
             } else
                 break;
        }
        struct Slice slice = { .P = P, .Q= Q };
        return slice;
    }