Reduce complexity in list operations

Question

I got a python problem to solve which I did, however I got some critics about the bad performance of the solution....so I wanted to share it here, and check for possible improvements:

The problem was vey simple, it is about finding the minimum absolute difference between the sum of the first part of a list and the sum of the second part.

As an example if we have:

L = [3, 1, 2, 4, 3]

We can split this in four stages:

i = 1, abs difference = |3 − 10| = 7 
i = 2, abs difference = |4 − 9| = 5 
i = 3, abs difference = |6 − 7| = 1 
i = 4, abs difference = |10 − 3| = 7 

In this example the script shall return 1 as the minimum absolute difference.

As I said, that was pretty easy for me and I did:

def get_minAbsDiff(L):
    return min([abs(sum(L[0:i+1]) - sum(L[i+1:])) for i in xrange(len(L)-1)])

However, seems like this is too time-complex solution O(N*N)

Would it be possible to get O(N) for this problem?

EDIT:

It was somebody else who told me about this O(N*N) complexity, I actually do not have any idea about if that is true for this example or not.

Answer 1

The key to achieving an O(N) solution is to recognize that as you move through the list, you are subtracting from one sum and adding to the other. So...

def get_minAbsDiff(L):
    leftSum = 0
    rightSum = sum(L)
    minDiff = rightSum

    for i in L:
        leftSum += i
        rightSum -= i
        diff = abs(leftSum-rightSum)

        if diff < minDiff: minDiff = diff

    return minDiff

Answer 2

You don't have to keep summing all elements. Create the sum once and update it in a loop:

def min_abs_diff(L):
    sum1, sum2 = 0, sum(L)
    min_abs_diff = float('inf')  # sentinel value
    for i in L:
        sum1 += i
        sum2 -= i
        abs_diff = abs(sum1 - sum2)
        if min_abs_diff > abs_diff:
            min_abs_diff = abs_diff
    return min_abs_diff

So you start with 0 and 13, then in the loop this becomes 3 and 10 as you shift the value of i over from one sum to the other.

Your solution is O(N*N) because the sum() function also loops. So for each iteration in your list comprehension, you take N steps as you sum all N elements into two totals, and you have N such iterations.