(Brilliant.org) Arrays Intermediate 3: Contiguous Knapsack

Question

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

• IEatBagels: 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.

Answer 1

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

• aghast: You don't need the deque. Just keep the running sum, and subtract items as you remove them from the tail.
• Graipher: @AustinHastings: True, you know the index of the item to subtract...
• Graipher: @AustinHastings: Added a version without summing the slice.
• Peilonrayz: Unless I'm missing something using a for loop would read better imo.
• Graipher: @Peilonrayz: True. Do you want to add it as your own answer, don't have time for it right now.

Answer 2

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