2
\$\begingroup\$

The problem consist of finding the longest contiguous subarray with a sum less than a given integer K.

The input data are:

  • K - the max sum
  • array - an array of integers

The algorithm I developed:

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 K, increment the head until the sum is less than K
   - while incrementing the tail check if we have a new max_length

The Python 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

My assumption is "this code is \$O(N)\$" because:

The worst case is when all elements are larger than K. In that case the while loop will increment the head and the tail successively so the number of iterations is \$2*N\$.

Is it true? If not, what's the complexity of this code?

\$\endgroup\$
5
  • \$\begingroup\$ This assumes that there are no negative numbers in the array? Is that a valid assumption? \$\endgroup\$
    – spyr03
    Nov 8, 2016 at 20:16
  • \$\begingroup\$ @spyr03 Yest it's! \$\endgroup\$
    – Chaker
    Nov 8, 2016 at 20:20
  • \$\begingroup\$ Being picky - array here is a python list? \$\endgroup\$
    – hpaulj
    Nov 9, 2016 at 8:18
  • \$\begingroup\$ @hpaulj yes the array is a Python list \$\endgroup\$
    – Chaker
    Nov 9, 2016 at 9:41
  • \$\begingroup\$ Maybe I'm nitpicking a bit, but if the specifications say less than, then it should be < K instead of <= K, right? \$\endgroup\$
    – ChatterOne
    Nov 9, 2016 at 12:07

1 Answer 1

4
\$\begingroup\$

Time complexity check

The best way to see if a function is indeed running in average linear time is to actually run it and look at the graph of size (N) vs time needed.

(Ask me if you are interested in the code used to generate this graph.)

Ask me if you are interested in the code used to generate this graph

There are a few outliers when the algorithm has to iterate more rather than less, but in general the trend is clearly linear.

Actual code review

As far as the code itself, you could yield the lengths and call max afterwards, to separate the code into finding all subarrays lengths and picking the max one: (this way finding all sub-arrays is just list(length_subarrays_more_than_k(array, K)))

def length_subarrays_more_than_k(array, K):
    head, tail = 0, 0
    current_sum = 0
    while(tail<len(array)):
        if current_sum + array[tail]<=K:
            current_sum += array[tail]
            tail += 1
            yield tail - head
        else:
            current_sum -= array[head]
            head += 1

def max_subarray_more_than_k(array, k):
    return max(length_subarrays_more_than_k(array, K))
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks!!! And of course I am interested in the code you used. \$\endgroup\$
    – Chaker
    Nov 8, 2016 at 21:32
  • \$\begingroup\$ @Chaker you can check it out on Git-Hub github.com/CAridorc/Plot-Benchmark , tell me what you think! \$\endgroup\$
    – Caridorc
    Nov 8, 2016 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.