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.

Answer 2

Original Answer

Initially the question was to find the length of the longest subarray that would sum to k.

You can run through the list indices, take each index as starting point of a window over which you sum. You then run over the indices from your starting index to the end to mark the end of the window. At each step you take the sum, or even better, add it to a sum term. If the sum exceeds the target you break out of the inner loop, moving on.

It will look like this:

def get_longes(a_list, k):
    longest = 0
    length = len(a_list)
    for i in xrange(length):
        s = 0
        for j in xrange(i,length):
            s+=a_list[j]
            if s < k:
                pass
            elif s==k:
                longest = j+1-i
            else:
                break
    return longest

This can be further speed up as you don't need to reset the window size when you move one step in the outer loop. In fact you just need to keep track of the window size and decrease it by 1 if the outer loop moves on. In this way you can even get rid of the inner loop and write something in O(n):

def get_longest(a_list,k):
    length=len(a_list)
    l_length = 0
    longest = 0
    s = 0
    for i in xrange(length):
        while s<k:  # while the sum is smaller, we increase the window size
            if i+l_length==length: # this could also be handled with a try, except IndexError on the s+=a_list[... line
                return longest
            s+=a_list[i+l_length]
            l_length+=1
        if s == k:  # if the sum is right, keep its length if it is bigger than the last match.
            longest = max(l_length, longest)
        l_length-=1  # keep the window end at the same position (as we will move forward one step)
        s-=a_list[i]  # and subtract the element that will leave the window
    return longest

Answer to Updated Question

The updated question asks for the longest subarray for which the sum is equal or less than k.

For this question, the basic approach is the same and actually the solution becomes even simpler as now we only have two conditions on the sum, that is:

1) the sum is smaller or equal to k.

2) the sum is bigger than k.

The solution looks like:

def get_longest_smaller_or_equal(a_list,k):
    length=len(a_list)
    l_length = 0
    longest = 0
    s = 0
    for i in xrange(length):
        while s<=k:  # while the sum is smaller, we increase the window size
            longest = max(l_length, longest)
            if i+l_length==length: # this could also be handled with a try, except IndexError on the s+=a_list[... line
                return longest
            s+=a_list[i+l_length]
            l_length+=1
        l_length-=1  # keep the window end at the same position (as we will move forward one step)
        s-=a_list[i]  # and subtract the element that will leave the window
    return longest