Length of longest subarray of sum less than or equal to k

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 1

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.

Original Answer

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.