Problem Description

Given an array of integers nums and an integer limit, your task is to find the length of the longest continuous subarray such that the absolute difference between any two elements in this subarray is less than or equal to limit.

In other words, for any subarray nums[i..j] (where i ≤ j), the following must be true for every pair of indices p and q in [i, j]:
|nums[p] - nums[q]| ≤ limit

Return the maximum possible length of such a subarray. Each element can be used only once per subarray, and you cannot reuse elements across different subarrays.

• Constraints:
  • 1 ≤ nums.length ≤ 10^5
  • 1 ≤ nums[i] ≤ 10^9
  • 0 ≤ limit ≤ 10^9

Thought Process

The initial idea might be to check every possible subarray and verify if the absolute difference between any two elements is within the limit. However, this brute-force approach is inefficient for large arrays, as it would require checking O(N^2) subarrays, and for each, possibly comparing all pairs, leading to O(N^3) time complexity.

To optimize, notice that for any subarray, the maximum absolute difference is simply the difference between its maximum and minimum elements. So we just need to ensure that max - min ≤ limit for the current window.

This insight leads us to use a sliding window approach, where we maintain a window [left, right] and efficiently keep track of the maximum and minimum values within the window. If at any point the difference exceeds the limit, we shrink the window from the left until the condition is satisfied again.

The challenge is how to efficiently get the min and max values in a moving window. Using data structures like balanced BSTs or double-ended queues (deques) allows us to do this in O(1) or O(logN) per operation.

Solution Approach

We'll use a sliding window combined with two deques:

• maxDeque: Maintains elements in decreasing order, so the front is always the maximum in the window.
• minDeque: Maintains elements in increasing order, so the front is always the minimum in the window.

1. Initialize two deques and two pointers: left and right at 0.
2. As you move right through the array:
   • Insert nums[right] into both deques, maintaining their monotonic properties (pop from back while necessary).
   • Check if the current window's max - min > limit (using the fronts of the deques).
   • If so, move left forward and remove elements from the deques if they're out of the window.
3. At each step, update the maximum window length seen so far.

This approach ensures that each element is added and removed from each deque at most once, resulting in linear time complexity.

Example Walkthrough

Example: nums = [8, 2, 4, 7], limit = 4

1. right = 0: Window is [8], max = 8, min = 8, diff = 0 ≤ 4. Window size = 1.
2. right = 1: Window is [8, 2], max = 8, min = 2, diff = 6 > 4.
   Shrink window from left: left = 1. Now window is [2], max = 2, min = 2, diff = 0.
3. right = 2: Window is [2, 4], max = 4, min = 2, diff = 2 ≤ 4. Window size = 2.
4. right = 3: Window is [2, 4, 7], max = 7, min = 2, diff = 5 > 4.
   Shrink window: left = 2. Window is [4, 7], max = 7, min = 4, diff = 3 ≤ 4. Window size = 2.

The longest valid subarray is [2, 4] or [4, 7], both of length 2. So the answer is 2.

Time and Space Complexity

• Brute-force approach: Checking all subarrays and their min/max takes O(N^2) time, where N is the length of nums. Space is O(1) (not counting input).
• Optimized approach (deque): Each element is added and removed from each deque at most once, so time complexity is O(N). Space complexity is O(N) in the worst case (if all elements are increasing or decreasing).

Summary

By recognizing that the maximum absolute difference in a subarray is simply the difference between its maximum and minimum, we can use a sliding window with monotonic deques to efficiently track the longest valid subarray. This approach avoids unnecessary repeated work and scales to large arrays, making it a practical and elegant solution to the problem.

Code Implementation

from collections import deque

class Solution:
    def longestSubarray(self, nums, limit):
        maxDeque = deque()
        minDeque = deque()
        left = 0
        res = 0

        for right, num in enumerate(nums):
            while maxDeque and num > maxDeque[-1]:
                maxDeque.pop()
            maxDeque.append(num)

            while minDeque and num < minDeque[-1]:
                minDeque.pop()
            minDeque.append(num)

            while maxDeque[0] - minDeque[0] > limit:
                if nums[left] == maxDeque[0]:
                    maxDeque.popleft()
                if nums[left] == minDeque[0]:
                    minDeque.popleft()
                left += 1

            res = max(res, right - left + 1)
        return res
      

#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> maxDeque, minDeque;
        int left = 0, res = 0;
        for (int right = 0; right < nums.size(); ++right) {
            while (!maxDeque.empty() && nums[right] > maxDeque.back())
                maxDeque.pop_back();
            maxDeque.push_back(nums[right]);

            while (!minDeque.empty() && nums[right] < minDeque.back())
                minDeque.pop_back();
            minDeque.push_back(nums[right]);

            while (maxDeque.front() - minDeque.front() > limit) {
                if (nums[left] == maxDeque.front())
                    maxDeque.pop_front();
                if (nums[left] == minDeque.front())
                    minDeque.pop_front();
                ++left;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();
        int left = 0, res = 0;
        for (int right = 0; right < nums.length; ++right) {
            while (!maxDeque.isEmpty() && nums[right] > maxDeque.getLast())
                maxDeque.removeLast();
            maxDeque.addLast(nums[right]);

            while (!minDeque.isEmpty() && nums[right] < minDeque.getLast())
                minDeque.removeLast();
            minDeque.addLast(nums[right]);

            while (maxDeque.getFirst() - minDeque.getFirst() > limit) {
                if (nums[left] == maxDeque.getFirst())
                    maxDeque.removeFirst();
                if (nums[left] == minDeque.getFirst())
                    minDeque.removeFirst();
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}
      

/**
 * @param {number[]} nums
 * @param {number} limit
 * @return {number}
 */
var longestSubarray = function(nums, limit) {
    let maxDeque = [];
    let minDeque = [];
    let left = 0, res = 0;
    for (let right = 0; right < nums.length; ++right) {
        while (maxDeque.length && nums[right] > maxDeque[maxDeque.length - 1])
            maxDeque.pop();
        maxDeque.push(nums[right]);

        while (minDeque.length && nums[right] < minDeque[minDeque.length - 1])
            minDeque.pop();
        minDeque.push(nums[right]);

        while (maxDeque[0] - minDeque[0] > limit) {
            if (nums[left] === maxDeque[0]) maxDeque.shift();
            if (nums[left] === minDeque[0]) minDeque.shift();
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
};