subvector sums (nearly) to zero

Tags:

Given a list of integers, find out a subvector whose sum is the nearest to (or equlas to ) zero.

#!/usr/bin/python

# Find a subvector of val_list whose sum is the nearest to the zero
def sub_vec_sum_nearest_to_zero(val_list):
    # cum_sum is a list containing (i, val_list[0] + ... val_list[i])
    cum_sum = [(0, val_list[0])]
    for i in xrange(1, len(val_list)):
        cum_sum.append((i, cum_sum[i - 1][1] + val_list[i]))

    # Sort cum_sum w.r.t. sum in descending order
    cum_sum.sort(lambda x, y: y[1] - x[1])

    # Find two successive elements from cum_sum whose difference
    # is the smallest. Suppose that a(i, s1) and b(j, s2) is such
    # elements. Then, s2 - s1 amounts to cum_sum[j] - cum_sum[i]
    # equals val_list[i + 1] + ... + val_list[j] if i < j.
    # If i > j, s1 - s2 amounts to val_list[j + 1] + ... + val[i].
    prev = cum_sum[0]
    near_min = ((None, None), None)
    for i in xrange(1, len(cum_sum)):
        cur = cum_sum[i]

        if near_min[1] is None or near_min[1] > abs(cur[1] - prev[1]):
           l = min(prev[0], cur[0]) + 1
           u = max(prev[0], cur[0])
           near_min = ((l, u), abs(cur[1] - prev[1]))

        prev = cur

    return near_min

# Should be ((1, 2), 1)
print sub_vec_sum_nearest_to_zero([1,3,-2,5])

# Should be ((3, 5), 0)
print sub_vec_sum_nearest_to_zero([3,-5,2,1,-7,6,4,2])

# Should be ((1, 10), 0)
print sub_vec_sum_nearest_to_zero([3,5,-1,-9,4,2,1,-12,5,3,2])

The first half of this program computes cumulative sums and it takes O(n), and therefore optimal. The second half finds out two values which is the same or nearly same from the cumulative sum vector in O(nlogn), and this problem boils down to element uniqueness whose lower bound is also O(nlogn).

Can anybody do better than me esp. in implementation? The code seems to be very messy (or is this the best what python can do?).

Reference: Programming Pearls. (Yes! It’s the best!)

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *