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

Problem statement

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

Solution

There are different ways to solve this problem: heaps with lazy updates, sorted list. There is also O(n) time complextity solution, using the idea of monotonic deque. We keep two of them: one with non-decreasing elements and another with non-increasing.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def longestSubarray(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