Problem statement

https://binarysearch.com/problems/Longest-Sublist-with-Absolute-Difference-Condition/

Solution

Equal to Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A, limit):
        Qmax, Qmin, i = deque(), deque(), 0
        for a in A:
            while Qmax and a > Qmax[-1]: Qmax.pop()
            while Qmin and a < Qmin[-1]: Qmin.pop()
            Qmax.append(a)
            Qmin.append(a)
            if Qmax[0] - Qmin[0] > limit:
                if Qmax[0] == A[i]: Qmax.popleft()
                if Qmin[0] == A[i]: Qmin.popleft()
                i += 1
        return len(A) - i