Algorithm - finding starting index of array so that sum of elements stays >= 0

Question

I was told that this can be done in O(n) - for time and O(n) for memory usage.

As input I recive a list of intigers (n in number - available from the start).

The task is to find the lowest index (first from left side) that enables me to go through the array (make a circle from the starting index to the index just behind that of the starting element) so that variable sum - that sums up all elements on the way never goes lower than 0.

*Sum off all elements in this array is always 0.

As example: 1, -1, -3, 3, 4, -4

1. 1 - 1 - 3 = -2 < 0 not that one
2. -1 < 0
3. -3 < 0
4. 3 + 4 - 4 + 1 - 1 - 3 = 0

is good beacause 7 > 0, 3 > 0, 4 > 0, 3 > 0, 0=0 :)

The way i do this now is I go into a for loop n times, inside i have two for loops: one for i->end index and the other for 0->i-1 index.

This works but is too slow, any ideas appreciated. (All language based program performance improvements were not enough)

Answer 1

From https://www.quora.com/Does-there-always-exist-a-rotation-of-a-circular-array-such-that-all-prefix-sums-for-that-rotation-are-non-negative-Given-that-sum-of-all-its-elements-is-non-negative:

Let the sequence be a(1),a(2),...,a(N) . Define s_a(i) = a(1)+a(2)+...+a(i). It is given that s_a(N)≥0 (assumption). Let j be the largest index such that s_a(j)<0 if such a j exists. Obviously, j < N . Consider the sequence a(j+1),a(j+2),...,a(N). It is easy to see that all prefix sums of this sequence are ≥0. If a(j+1)+a(j+2)+...+a(k) were less than 0, s_a(k) would have been less than 0 as well, a contradiction.

Now generate a new sequence {bi} = a(j+1),a(j+2),...,a(N),a(1),a(2),...,a(j). It is easy to see that the prefix sums of this new sequence (call it s_b(i)) do not attain a value less than zero for the first N-j elements. Also, since s_b(N-j)≥0, Had s_a(i) been nonnegative, s_b(i+N-j) would be as well.

Keep repeating the process of taking the section after the rightmost position with a negative prefix sum and bringing it to the beginning of the sequence. At each step, the starting range in which we are assured that the prefix sums will be nonnegative keeps increasing. But this number is bounded by N, the length of the sequence. This means that after some steps, there will be no negative prefix sum in the sequence. Thus we have obtained a rotation of the original sequence with all prefix sums nonnegative.

This is the simple O(n) implementation for my idea.

int best_index(std::vector<int> & a){
    int n = A.size();

    long long array_sum=0;
    long long sum=0;
    int last_index=-1;
    for (int i = 0; i < n; ++i)
    {
        array_sum+=a[i];
        if (sum<0)
        {
            sum=0;
            if (a[i]>=0)
            {
                last_index=i;
            }
        }
        sum+=a[i];
    }

    if (array_sum<0)
    {
        return -1;
    }
    return last_index;
}

Complexity: O(n)

Answer 2

We start by accumulating the sum of the elements:

elements = [1, -1, -3, 3, 4, -4]
sums =     [1,  0, -3, 0, 4,  0]

(If the last value is negative, there is no solution)

So if we started at index 0, we'd get this sequence. If we started at index 1, all the numbers would decrease by one (and rotate around, but we don't care for that). If we started at index 2, the numbers wouldn't be different. We can see that by choosing the starting point, we can move the entire sequence up and down by the values of the skipped numbers.

Our aim is to lift the entire sequence high enough so that no value becomes negative. For that, we have to start right after the minimum - or, if there are multiple ones, after the first minimum.

We can find that easily in O(n):

startingIndex (elements):
    sums = []
    sum = 0
    for (i = 0; i < elements.length; i++)
        sums[i] = sum
        sum += elements[i]
    if (sum < 0)
        throw "invalid input"
    min = 0
    index = 0
    for (i = 0; i < elements.length; i++)
        if (sums[i] < min)
            min = sums[i]
            index = i
    return index