Finding minimal absolute sum of a subarray

Question

There's an array A containing (positive and negative) integers. Find a (contiguous) subarray whose elements' absolute sum is minimal, e.g.:

A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum

I've started by implementing a brute-force algorithm which was O(N^2) or O(N^3), though it produced correct results. But the task specifies:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

After some searching I thought that maybe Kadane's algorithm can be modified to fit this problem but I failed to do it.

My question is - is Kadane's algorithm the right way to go? If not, could you point me in the right direction (or name an algorithm that could help me here)? I don't want a ready-made code, I just need help in finding the right algorithm.

Solution 1

If you compute the partial sums such as

2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)...

Then the sum of any contiguous subarray is the difference of two of the partial sums. So to find the contiguous subarray whose absolute value is minimal, I suggest that you sort the partial sums and then find the two values which are closest together, and use the positions of these two partial sums in the original sequence to find the start and end of the sub-array with smallest absolute value.

The expensive bit here is the sort, so I think this runs in time O(n * log(n)).

Solution 2

This is C++ implementation of Saksow's algorithm.

int solution(vector<int> &A) {
    vector<int> P;
    int min = 20000 ;
    int dif = 0 ;
    P.resize(A.size()+1);
    P[0] = 0;
    for(int i = 1 ; i < P.size(); i ++)
    {
        P[i] = P[i-1]+A[i-1];

    }
    sort(P.begin(),P.end());
    for(int i = 1 ; i < P.size(); i++)
    {
         dif = P[i]-P[i-1];
         if(dif<min)
         {
             min = dif;
         }
    }
    return min;
}

Solution 3

I was doing this test on Codility and I found mcdowella answer quite helpful, but not enough I have to say: so here is a 2015 answer guys!

We need to build the prefix sums of array A (called P here) like: P[0] = 0, P[1] = P[0] + A[0], P[2] = P[1] + A[1], ..., P[N] = P[N-1] + A[N-1]

The "min abs sum" of A will be the minimum absolute difference between 2 elements in P. So we just have to .sort() P and loop through it taking every time 2 successive elements. This way we have O(N + Nlog(N) + N) which equals to O(Nlog(N)).

That's it!

Solution 4

The answer is yes, Kadane's algorithm is definitely the way to go for solving your problem.

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Source - I've closely worked with a PhD student who's entire PhD thesis was devoted to the maximum subarray problem.

View more solutions

Comments

[Maresh]

I'm curious to see how you implemented that.

[Saksow]

I implemented it in Python but I don't have the code any more... What is the part that interests you the most ? I can explain more.

[Benubird]

I'm not following how you identify the subarray from the partial sums. for instance the array [-4,5,-1] has partial sums [-4,1,0], which you seem to imply means that the subarray should be [5,-1]=4, whereas the actual solution is [-4,5,-1]=0.

[Benubird]

What about this array [-5,8,-1]? the P is [0,-5,3,2], so the min abs diff between P elements is 1 (2,3), but the min abs sum of A is 2 (-5,8,-1). Or this one: [14,-4,5] which gives P [0,12,10,15], so the min diff of P is 2 (10,12), but of A is 1 (-4,5)

[mcdowella]

I didn't consider the entire array, considered as a sub-array. You could either consider subarrays with small partial sums separately, or be sure to include the sub-array with zero elements in it when you sort everything - this has a sum of zero, so in your example you would have partial sums [-4,1,0,0] and spot the solution that comes from considering the span between the end of the terms summed by the two zero sums - the beginning and end of the entire array. The subarray identified from two partial sums is the set of items in the partial sum with most items summed but not in the other.

[Saksow]

You are right in the first example. But for [14,-4,5] you built P wrongly it should be [0,14,10,15] which gives the min diff 1. Can you look for a fully working solution ?

[Catalyst]

Consider 3,3,3,4,5 ? Maybe I'm confused.

[mcdowella]

Partial sums 0,3,6,9,13,18 (including partial sum of first 0 elements) which is already sorted and 3,6 is a pair of numbers closest together so one answer for the contiguous sub-array with smallest absolute partial sum is [3]. As far as I can tell this is the correct answer, unless you allow the zero length partial sum, which would be the correct answer for every input if you allowed it.

[Saksow]

@Salivan there is cases where it doesn't work but I think it's not too far from the correct solution

[Soley]

Thanks for the reply. However that fails for the 100%. I was curious for their own specific answer using DP, but it requires too much to understand it (as I do the tests for fun). So I just converted the solution into Java.

[Saksow]

It sure worked for many cases, you can see my reply above for an example, good luck!

[paparazzo]

This fails to address the absolute

[Horia Toma]

will it work for -1,-2,-3? when you compute the result, you should consider the partial sums, too, not only the differences between them.