nonsequiter - 6 months ago 83

Python Question

In an interview I was asked this question: given some array of positive integers s, find the length of the longest subarray such that the sum of all its values is less than or equal to some positive integer k. Each input will always have at least one solution. The array is not circular.

I began writing a dynamic programming solution that worked by finding the maximum length at increasingly larger values from 0 to k.

Here is my code in python, there is an error inside it that I couldn't seem to find, my answer is always off by a few digits:

`def maxLength(s, k):`

lengths = [0 for x in range(k)]

for i in range(1,k+1):

for j in range(len(s)):

if s[j] <= i and lengths[i - s[j]] + 1 > lengths[i]:

lengths[i] = lengths[i - s[j]] + 1

if i + 1 == len(s):

break

return lengths[-1]

Input1:

`s = [1,2,3], k = 4`

Output1:

`2`

Input2:

`s=[3,1,2,1], k = 4`

Output2:

`3`

Answer

You can do this in linear (O(n)) time:

def max_length(s, k):
# These two mark the start and end of the subarray that `current`

used to be.
subarray_start = 0
subarray_end = 0

```
subarray_sum = 0
max_len = -1 # returns -1 if there is no subsequence that adds up to k.
for i in s:
subarray_sum += i
subarray_end += 1
while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
subarray_sum -= s[subarray_start]
subarray_start += 1
# After the previous while loop, subarray_sum is guaranteed to be
# smaller than or equal to k.
max_len = max(max_len, subarray_end - subarray_start)
return max_len
```

There was some confusion with the original question, where I thought we were looking for a subarray with sum **equal to (but not less than) k*. My original answer is below. There's information about the linearity of this solution in there as well, so read on if you're interested.

Here's how I would do it:

```
def max_length(s, k):
current = []
max_len = -1 # returns -1 if there is no subsequence that adds up to k.
for i in s:
current.append(i)
while sum(current) > k: # Shrink the array from the left, until the sum is <= k.
current = current[1:]
if sum(current) == k:
max_len = max(max_len, len(current))
return max_len
```

This exploits the fact that we're looking for a contiguous subarray to get a solution with linear (O(n)) time complexity. `current`

is our current attempt at creating a subarray that adds up to `k`

. We loop through `s`

and add every element from `s`

to `current`

. If the total sum of `current`

becomes too large (larger than `k`

), we remove elements from the left of `current`

until the sum is smaller than or equal to `k`

. If at any point, the sum is equal to `k`

, we record the length.

Well... I lied, and Francisco Couzo caught me in the comments. The code above is not really O(n) I'm calling `len(current)`

and `sum(current)`

, which take at most `n`

steps, making the algorithm run in quadratic time (O(n^2)). We can fix this by keeping track of the size and sum of `current`

ourselves.

The version below gets us closer to O(n), but I noticed an issue while writing it.

```
def max_length(s, k):
current = []
len_current = 0
sum_current = 0
max_len = -1 # returns -1 if there is no subsequence that adds up to k.
for i in s:
current.append(i)
sum_current += i
len_current += 1
while sum_current > k: # Shrink the array from the left, until the sum is <= k.
sum_current -= current[0]
current = current[1:]
len_current -= 1
if sum_current == k:
max_len = max(max_len, len_current)
return max_len
```

This piece of code might look like it's O(n), and if it were written in Go, it would be. See that `current = current[1:]`

? According to the TimeComplexities article in the Python wiki, taking a slice from a list takes O(n).

I couldn't find a list operation that removes an element from the start, until I suddenly realized that I didn't have to. `current`

would always be a contiguous subarray of `s`

, so why not just mark its start and end?

So here's my final solution:

```
def max_length(s, k):
# These two mark the start and end of the subarray that `current` used to be.
subarray_start = 0
subarray_end = 0
subarray_sum = 0
max_len = -1 # returns -1 if there is no subsequence that adds up to k.
for i in s:
subarray_sum += i
subarray_end += 1
while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
subarray_sum -= s[subarray_start]
subarray_start += 1
if subarray_sum == k:
max_len = max(max_len, subarray_end - subarray_start)
return max_len
```

If you consider the array to be circular, which the first example case in the question seems to indicate, you can go through the array twice:

```
def max_length(s, k):
s = s + s
# These two mark the start and end of the subarray that `current` used to be.
subarray_start = 0
subarray_end = 0
subarray_sum = 0
max_len = -1 # returns -1 if there is no subsequence that adds up to k.
for i in s:
subarray_sum += i
subarray_end += 1
while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
subarray_sum -= s[subarray_start]
subarray_start += 1
if subarray_sum == k:
max_len = max(max_len, subarray_end - subarray_start)
return max_len
```

There are probably checks you can make to break out of that second pass sooner, based on the values you've encountered in the first pass.