List iteration optimization

Question

I'm trying to create a function to find the longest segment within a given list t, which satisfies two conditions:

1. The last number of the segment has to be equal or greater than the first number of the segment.

2. Difference between the last number and the first number of the segment has to be equal or less than a given integer x.

I'm able to create a working piece of code, but it is too slow. I can't come up with a solution that would not utilize 'nested for-loops'.

The algorithm should work with lists up to 10^5 integers, each integer random from 1 <= x <= 10^9.

def find(t: list, x: int):
    n = len(t)
    max_len = 0

    for i in range(n):
        for j in range(i, n):
            if t[j] >= t[i] and t[j] - t[i] <= x:
                max_len = max(max_len, j - i + 1)

    return max_len

if __name__ == "__main__":
    print(find([1, 4, 6], 1)) # 1
    print(find([1, 4, 6], 10)) # 3
    print(find([4, 1, 10, 5, 14], 1)) # 4
    print(find([4, 1, 10, 5, 14], 10)) # 5
    print(find([9, 8, 7, 6, 5, 4, 3, 2, 1], 100)) # 1

Answer 1

O(n log n) solution: Visit the values in increasing order, considering them as right endpoint. Keep the still relevant possible left endpoints in a monoqueue of increasing values and increasing indices. A value stops being a left endpoint candidate when

• it becomes too small (for the current value and thus also for all remaining right endpoint candidates, as they are only getting bigger) or
• its index is larger than the current value's index (because then the current value/index will always be a better left endpoint candidate for the remaining right endpoint candidates).

from collections import deque

def find(t: list, x: int):
    IV = deque()
    result = 1
    for i, v in sorted(enumerate(t), key=lambda e: e[1]):
        while IV and IV[0][1] < v - x:
            IV.popleft()
        if IV:
            result = max(result, i - IV[0][0] + 1)
        while IV and IV[-1][0] > i:
            IV.pop()
        IV.append((i, v))
    return result

Attempt This Online!