Find the longest subarray with sum less than K
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.)



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&lt;len(array)):
        if current_sum + array[tail]&lt;=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))