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

How it works

We want the longest continuous subarray where the difference between the maximum and minimum values is at most limit.

A sliding window works well because the subarray must be continuous. As we expand the window to the right, we need to always know the current minimum and maximum in the window.

To track them efficiently, we maintain two monotonic deques:

• inc (increasing deque): keeps possible minimum values in increasing order, so the front is the current minimum
• dec (decreasing deque): keeps possible maximum values in decreasing order, so the front is the current maximum

Whenever the window becomes invalid (max - min > limit), we shrink it from the left by moving j forward and removing the left element from the deques if it matches their front.

Steps

1. Initialize two deques using the first element:
   • inc for minimum tracking (monotonic increasing)
   • dec for maximum tracking (monotonic decreasing)
2. Use two pointers:
   • i expands the window to the right
   • j shrinks the window from the left when needed
3. For each new element nums[i]:
   • Maintain inc by popping from the back while the back is greater than nums[i]
   • Maintain dec by popping from the back while the back is less than nums[i]
   • Append nums[i] to both deques
4. If the window becomes invalid (dec[0] - inc[0] > limit):
   • If the element leaving the window (nums[j]) equals the front of dec, pop it from dec
   • If it equals the front of inc, pop it from inc
   • Move j forward by 1 to shrink the window
5. After processing all elements, the valid window starts at j and ends at the last index, so its length is len(nums) - j
6. Return that length

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Using Regular Queues Instead of Monotonic Deques

A common mistake is to use regular queues or simply track a single max and min value. When the window shrinks, you lose track of the next maximum or minimum. Monotonic deques maintain candidates in order so that the front always gives the current extreme value for the window.

Removing the Wrong Element When Shrinking the Window

When the left pointer moves, you must only remove elements from the deques if they match the element leaving the window. A subtle bug occurs when you pop from the deque unconditionally, which can remove elements that are still inside the valid window.

Not Maintaining Deque Invariants Correctly

For the min deque to work correctly, it must remain monotonically increasing from front to back. For the max deque, it must remain monotonically decreasing. Forgetting to pop elements that violate these invariants before adding a new element leads to incorrect min/max values.

Comparing Indices Instead of Values

When using deques that store indices instead of values, a common mistake is to compare indices when you should compare values, or vice versa. Be consistent about what the deque stores and ensure comparisons use the appropriate array lookups.

Off-by-One Errors in Window Size Calculation

The window size is right - left + 1, not right - left. Forgetting the +1 when updating the result will undercount the longest valid subarray by one element.

from typing import List
from collections import deque

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        inc = deque([nums[0]])
        dec = deque([nums[0]])
        res = 1
        j = 0

        for i in range(1, len(nums)):
            while inc and inc[-1] > nums[i]:
                inc.pop()
            while dec and dec[-1] < nums[i]:
                dec.pop()

            inc.append(nums[i])
            dec.append(nums[i])
            if dec[0] - inc[0] > limit:
                if dec[0] == nums[j]:
                    dec.popleft()
                if inc[0] == nums[j]:
                    inc.popleft()
                j += 1

        return len(nums) - j

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> inc, dec;
        inc.push_back(nums[0]);
        dec.push_back(nums[0]);
        int res = 1, j = 0, n = nums.size();

        for (int i = 1; i < n; i++) {
            while (!inc.empty() && inc.back() > nums[i]) {
                inc.pop_back();
            }
            while (!dec.empty() && dec.back() < nums[i]) {
                dec.pop_back();
            }

            inc.push_back(nums[i]);
            dec.push_back(nums[i]);
            if (dec.front() - inc.front() > limit) {
                if (dec.front() == nums[j]) {
                    dec.pop_front();
                }
                if (inc.front() == nums[j]) {
                    inc.pop_front();
                }
                j++;
            }
        }

        return n - j;
    }
};