Chaker Benhamed

Home | |

Find the longest subset with sum less than K

over 4 years ago.

In the course of finding an internship I applied to bunch of the top tech companies. Some refused my application, other ignore it. One gave me a programming challenge (I can't say the name unfortunately) in which I got a couple of interesting problems to solve.

One of the problems consist of finding the longest subset with a sum less than a given integer.

The input data are:

* 'K' the max sum

* 'a' an array of integers

my first approach as always is "don't reinvent the wheel" and Google it to find the optimal algorithm. However this is a challenge in which my programming skills are tested so I grabbed pen and papers and start with the most obvious way.

- start at the "start" position - start summing up until we go over K - save the length - increment the "start" position - and repeat

In python

def length_max_subarray(a, K): length = 0 start = 0 finish = 0 while(start<len(a)): finish = 0 s = sum(a[start:start+finish]) while(start+finish<=len(a) and s<=K ): if finish > length: length = finish finish+=1 s = sum(a[start:start+finish]) start+=1 return length

As you can see this is in the order of **O( N ^{2} )** of course we can save some steps for example we don't need to reset the finish to zero we can directly set it up to length

.... while(start<len(a)): finish = length s = sum(a[start:start+finish]) while(start+finish<=len(a) and s<=K ): ....

However this doesn't give us a performance boost we need to find a solution to lower the order of magnitude

I got the idea of using a **head** and **tail** and keep the current sum

head = tail = 0 -while the tail is less than the length of the array -increment the tail and update the sum -if the sum go over the max sum increment the head until the sum is less than K - while incrementing the tail check if we have a new max_length

The code:

def length_max_subarray(array, K): head, tail = 0, 0 length = 0 current_sum = 0 while(tail<len(array)): if current_sum + array[tail]<=K: current_sum += array[tail] tail+=1 if tail-head > length: length = tail-head else: current_sum -= array[head] head+=1 return length

As you can see this is in the order of **O(N)**.

Unfortunately I was busy with exams so I didn't give my full potential. Anyway if you had another ideas or suggestions you can find my on twitter.