AlgoMaster Logo

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

Last Updated: March 29, 2026

medium
4 min read

Understanding the Problem

We need to find the longest contiguous subarray where the difference between the maximum and minimum elements is at most limit. The key observation is that "the absolute difference between any two elements <= limit" is equivalent to max(subarray) - min(subarray) <= limit. If the overall spread fits within the limit, every pair of elements automatically satisfies the condition too.

So the problem reduces to: find the longest window [left, right] where max(window) - min(window) <= limit. The challenge is efficiently tracking the current min and max as the window slides.

Key Constraints:

  • 1 <= nums.length <= 10^5 -- With n up to 100,000, we need O(n log n) or better. A brute force O(n^2) approach risks TLE.
  • 1 <= nums[i] <= 10^9 -- Large values, but we only care about differences, so this doesn't affect our algorithm choice.
  • 0 <= limit <= 10^9 -- The limit can be 0 (only identical elements allowed) or very large (the whole array might be valid).

Approach 1: Brute Force

Intuition

The simplest approach is to examine every possible subarray and check whether the spread fits within the limit. For each starting index i, we extend the subarray one element at a time, maintaining a running min and max. The moment the spread exceeds the limit, we stop, because adding more elements can only make the spread worse (or keep it the same, but never improve it).

We track the longest valid subarray seen so far.

Algorithm

  1. Initialize maxLen = 1 (every single element is a valid subarray).
  2. For each starting index i from 0 to n-1:
    • Set currentMin = nums[i] and currentMax = nums[i].
    • For each ending index j from i+1 to n-1:
      • Update currentMin and currentMax with nums[j].
      • If currentMax - currentMin > limit, break.
      • Otherwise, update maxLen = max(maxLen, j - i + 1).
  3. Return maxLen.

Code

For each starting index, we scan forward through the array, throwing away all the min/max information when we move to the next start. What if we used a sliding window that only moves forward and tracked the min and max efficiently?

Approach 2: Sliding Window with Sorted Map

Intuition

Instead of restarting for each starting index, we can use a sliding window [left, right] that only expands and shrinks forward. As we move right forward, we add the new element. If the window becomes invalid (spread > limit), we shrink from the left until it's valid again.

The challenge is: when we remove an element from the left, how do we know the new min and max? A simple variable won't work because the element we're removing might be the current min or max, and we'd have no way to find the next one without rescanning.

This is where a sorted data structure helps. A TreeMap (Java), SortedList (Python), or multiset (C++) keeps elements in sorted order with O(log n) insertion and deletion. The first key gives us the min, the last key gives us the max.

Algorithm

  1. Initialize left = 0, maxLen = 0, and a sorted frequency map.
  2. For each right from 0 to n-1:
    • Add nums[right] to the frequency map.
    • While the spread (last key - first key) > limit:
      • Decrement the frequency of nums[left]. Remove the key if frequency hits 0.
      • Increment left.
    • Update maxLen = max(maxLen, right - left + 1).
  3. Return maxLen.

Example Walkthrough

1Initialize: left=0, right=0, freq={8:1}, spread=0 <= 4, maxLen=1
0
right
8
left
window
1
2
2
4
3
7
1/7

Code

The sorted map maintains full sorted order, but we only ever query the max and min. What if we used a data structure that tracks only those two extremes in amortized O(1)?

Approach 3: Sliding Window with Monotonic Deques (Optimal)

Intuition

We only need the max and min of the current window. Monotonic deques are tailor-made for this. A decreasing deque tracks the maximum: its front always holds the index of the largest element in the window. An increasing deque tracks the minimum: its front holds the index of the smallest element.

When we add a new element at index right, for the max deque we pop all elements from the back that are smaller than or equal to nums[right] (they can never be the max while nums[right] is in the window), then push right. The min deque works symmetrically. When we shrink from the left, we check if the deque fronts have fallen out of the window and pop them.

Each element enters and leaves each deque exactly once, giving us amortized O(1) per element, and O(n) total.

Algorithm

  1. Initialize left = 0, maxLen = 0, and two deques: maxDeque (decreasing values) and minDeque (increasing values).
  2. For each right from 0 to n-1:
    • Maintain the max deque: pop from the back while the back value <= nums[right], then push right.
    • Maintain the min deque: pop from the back while the back value >= nums[right], then push right.
    • While nums[maxDeque.front] - nums[minDeque.front] > limit:
      • Increment left.
      • If maxDeque.front < left, pop the front.
      • If minDeque.front < left, pop the front.
    • Update maxLen = max(maxLen, right - left + 1).
  3. Return maxLen.

Example Walkthrough

1right=0: nums[0]=10, maxDeque=[0], minDeque=[0], spread=0 <= 5, maxLen=1
0
right
10
left
window
1
1
2
2
3
4
4
7
5
2
1/8

Code