Minimum Subarray Difference In Python

Consider I have a non-empty array of integers: A0..An. And consider a parameter P where 0 < P <=n. I need to find a minimum absolute difference between left and right subarra

Solution 1:

This is more concise yet still O(n):

import itertools

def min_diff(A):
    total = sum(A)
    return min(abs(total - lsum - lsum) for lsum in itertools.accumulate(A))

itertools.accumulate is available from Python 3.2 up.

Solution 2:

The bug is this:

if next < diff:
    diff = next
    p += 1
else:
    return diff

You terminate if next is not improving on diff. This is wrong, since you still might find a better solution later on.

Other than that, I think your idea goes in the right direction. What you should do to fix your bug is go through the whole array unconditionally and just return diffin the end. Like so:

def solution(A):
    lsum, rsum = A[0], sum(A[1:])
    diff = abs(rsum - lsum)
    p = 1
    while p < (len(A)-1):
        lsum += A[p]
        rsum -= A[p]
        next = abs(rsum - lsum)
        if next < diff:
            diff = next
        p += 1
    return diff

(Note: I tried to modify as little as possible, i.e. to stay as close to your code as possible. Also, I did not really test this. But I hope you get the idea.)

Solution 3:

EDIT (the previous solution had a high complexity, my bad)

This is a remake of yours, but getting rid of the indexing on the list and using the min built-in function to get the minimum.

def solution(a):
    lsum = a[0]
    rsum = sum(a)-lsum
    dfs = [abs(rsum-lsum),]
    for el in a[1:]:
        lsum+=el
        rsum-=el
        dfs.append(abs(rsum-lsum))
    return min(dfs)

calling it with

sol = solution([3,1,2,4,3])
print(sol)

produces

1