Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit LeetCode solution in Python

1
# max absolte diff within a subarray is subarray max substracted by subarray min
2
class Solution:
3
    def longestSubarray(self, nums: List[int], limit: int) -> int:
4
        q = (
5
            collections.deque()
6
        )  # monotonic decreasing deque to compute subarray max, index of
7
        q2 = (
8
            collections.deque()
9
        )  # monotonic increasing deque to compute subarray min, index of
10

11
        # sliding window
12
        res = left = 0
13
        for right in range(len(nums)):
14
            # pop monotocity-violating numbers from right end
15
            while q and nums[q[-1]] <= nums[right]:
16
                q.pop()
17
            q.append(right)
18

19
            # pop monotocity-violating numbers from right end
20
            while q2 and nums[q2[-1]] >= nums[right]:
21
                q2.pop()
22
            q2.append(right)
23

24
            # sliding window
25
            while left < right and q and q2 and nums[q[0]] - nums[q2[0]] > limit:
26
                # compress window from left pointer
27
                if q and q[0] == left:
28
                    q.popleft()
29

30
                # compress left pointer
31
                if q2 and q2[0] == left:
32
                    q2.popleft()
33

34
                left += 1
35

36
            if nums[q[0]] - nums[q2[0]] <= limit:
37
                res = max(res, right - left + 1)
38

39
        return res