1
\$\begingroup\$

Problem

Given an array and a number \$t\$, write a function that determines if there exists a contiguous sub-array whose sum is \$t\$.

Source (Note that the URL may not link to the exact problem as it's from a quiz site, and questions seem to be randomly generated).

I was able to come up with a \$O(n^2)\$ solution, and further thinking hasn't improved upon it:

def substring_sum(lst, target):
    sums = []
    for val in lst:
        if val == target:
            return True
        for idx, _ in enumerate(sums):
            sums[idx] += val
            if sums[idx] == target:
                return True
        sums.append(val)
    return False
\$\endgroup\$
  • 4
    \$\begingroup\$ Hey Tobi, if you're not sure the URL doesn't link to the right problem, don't put it in your post. It would be better to give some examples of the problem. \$\endgroup\$ – IEatBagels Mar 15 at 15:17
7
\$\begingroup\$

You are currently calculating the sum of all possible subarrays. A different approach is to imagine a sliding window on the array. If the sum of the elements in this window is smaller than the target sum, you extend the window by one element, if the sum is larger, you start the window one element later. Obviously, if the sum of the elements within the window is the target, we are done.

This algorithm only works if the array contains only non-negative numbers (as seems to be the case here when looking at the possible answers).

Here is an example implementation:

def contiguous_sum(a, target):
    start, end = 0, 1
    sum_ = sum(a[start:end])
    # print(start, end, sum_)
    while sum_ != target and start < end < len(a):
        if sum_ < t:
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
        sum_ = sum(a[start:end])
        # print(start, end, sum_)
    return sum_ == target

This algorithm can be further improved by only keeping a running total, from which you add or subtract:

def contiguous_sum2(a, t):
    start, end = 0, 1
    sum_ = a[0]
    #print(start, end, sum_)
    while sum_ != t and start < end < len(a):
        if sum_ < t:
            sum_ += a[end]
            end += 1
        else:
            sum_ -= a[start]
            start += 1
            if start == end:
                sum_ += a[end]
                end += 1
        #print(start, end, sum_)
    return sum_ == t

The implementation can be streamlined further by using a for loop, since we actually only loop once over the input array, as recommended in the comments by @Peilonrayz:

def contiguous_sum_for(numbers, target):
    end = 0
    total = 0
    for value in numbers:
        total += value
        if total == target:
            return True
        while total > target:
            total -= numbers[end]
            end += 1
    return False

All three functions are faster than your algorithm for random arrays of all lengths (containing values from 0 to 1000 and the target always being 100):

enter image description here

\$\endgroup\$
  • \$\begingroup\$ You don't need the deque. Just keep the running sum, and subtract items as you remove them from the tail. \$\endgroup\$ – Austin Hastings Mar 15 at 16:05
  • \$\begingroup\$ @AustinHastings: True, you know the index of the item to subtract... \$\endgroup\$ – Graipher Mar 15 at 16:07
  • 1
    \$\begingroup\$ @AustinHastings: Added a version without summing the slice. \$\endgroup\$ – Graipher Mar 15 at 16:23
  • 2
    \$\begingroup\$ Unless I'm missing something using a for loop would read better imo. \$\endgroup\$ – Peilonrayz Mar 15 at 16:48
  • \$\begingroup\$ @Peilonrayz: True. Do you want to add it as your own answer, don't have time for it right now. \$\endgroup\$ – Graipher Mar 15 at 16:49
0
\$\begingroup\$

It is possible to do better than the \$O(n^2)\$ of my original solution and solve it in linear time by using a set to store the sums at each point and comparing if the sum at this point minus the target is in the set. However this solution uses \$O(n)\$ space:

def substring_sum(lst, target):
    sm = 0
    sums = {sm}
    for val in lst:
        sm += val
        if sm - target in sums:
            return True
        sums.add(sm)
    return False    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.