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

Intuition

To decide if a window is valid we only need its current maximum and minimum, so we maintain two monotonic deques of indices. The max deque stays decreasing, so its front is always the largest value in the window; the min deque stays increasing, so its front is always the smallest. As the right pointer expands, we pop from the back of each deque any indices whose values can no longer be the max or min, then append the new index. Whenever the front difference exceeds the limit, the window is invalid, so we move the left pointer forward and discard any deque front that has slid out of the window. The widest window that stays valid is the answer.

Algorithm walkthrough

1. 1Create an empty max deque (kept decreasing by value) and an empty min deque (kept increasing by value), both storing indices; set left and best to 0.
2. 2For each right index, pop indices from the back of the max deque while their value is less than or equal to nums[right], then push right; do the mirror operation on the min deque, popping while their value is greater than or equal to nums[right].
3. 3The fronts of the two deques now give the maximum and minimum of the current window.
4. 4While nums[maxDeque.front] - nums[minDeque.front] exceeds limit, advance left, and if a deque's front index is now before left, pop it from the front.
5. 5Once the window is valid again, update best with right - left + 1.
6. 6After processing every index, return best.

Implementation

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        from collections import deque
        max_dq = deque()  # decreasing values
        min_dq = deque()  # increasing values
        left = 0
        best = 0
        for right in range(len(nums)):
            while max_dq and nums[max_dq[-1]] <= nums[right]:
                max_dq.pop()
            max_dq.append(right)
            while min_dq and nums[min_dq[-1]] >= nums[right]:
                min_dq.pop()
            min_dq.append(right)
            while nums[max_dq[0]] - nums[min_dq[0]] > limit:
                left += 1
                if max_dq[0] < left:
                    max_dq.popleft()
                if min_dq[0] < left:
                    min_dq.popleft()
            best = max(best, right - left + 1)
        return best