AlgoMaster Logo

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

mediumFrequency7 min readUpdated June 23, 2026

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 condition "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 satisfies the condition, because the largest pairwise difference in any set is between its extremes.

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

Key Constraints:

  • 1 <= nums.length <= 10^5: with n up to 100,000, an O(n^2) scan can reach 10^10 operations in the worst case (for example, all elements equal), so we want O(n log n) or better.
  • 1 <= nums[i] <= 10^9: values are large, but we only compare differences, so the magnitudes do not affect the algorithm. The values fit in a 32-bit integer, and the largest spread (about 10^9) also fits, so no overflow concern.
  • 0 <= limit <= 10^9: the limit can be 0 (only runs of identical elements qualify) or large enough that the whole array is one valid window.

Approach 1: Brute Force

Intuition

Examine every subarray and check whether its spread fits within the limit. For each starting index i, extend the subarray one element at a time while maintaining a running min and max. Once the spread exceeds the limit, stop extending from this start: adding more elements can only widen the spread or leave it unchanged, never shrink it, so no longer subarray starting at i can become valid again.

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

This discards all the min and max information each time the start advances. A sliding window that moves forward only, without resetting, avoids that wasted work.

Approach 2: Sliding Window with Sorted Map

Intuition

Instead of restarting for each starting index, use a sliding window [left, right] that advances both ends in one direction. As right moves forward, add the new element. When the window becomes invalid (spread > limit), shrink from the left until it is valid again.

Removing an element from the left raises a problem: if that element was the current min or max, a single tracking variable cannot tell us the next min or max without rescanning the window. An ordered map solves this. A TreeMap (Java), SortedList (Python), map (C++), or BTreeMap (Rust) keeps the window's elements in sorted order with O(log n) insertion and deletion. The first key is the min, the last key is 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 ordered map maintains a full sort, but the algorithm only ever reads the max and min. Two monotonic deques track exactly those two extremes in amortized O(1), dropping the log factor and the sorted-container overhead.

Approach 3: Sliding Window with Monotonic Deques (Optimal)

Intuition

The algorithm only reads the max and min of the current window, so we maintain those two values with monotonic deques of indices. A decreasing deque tracks the maximum: its front holds the index of the largest element in the window. An increasing deque tracks the minimum: its front holds the index of the smallest.

When a new element arrives at index right, the max deque pops from the back every index whose value is less than or equal to nums[right]. Those elements are both older and no larger than nums[right], so while nums[right] stays in the window they can never be the maximum, and they leave the window before it does. After popping, push right. The min deque is symmetric, popping back values greater than or equal to nums[right]. When the window shrinks, a front index that has fallen below left is popped, since it now points outside the window.

Each index enters and leaves each deque at most once, so the deque work is 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