# (Brilliant.org) Arrays Intermediate 3: Contiguous Knapsack

## 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

• 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. Mar 15 '19 at 15:17

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):

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

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