Problem

Given an integer array nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between the maximum and minimum element in the subarray is less than or equal to limit.

Examples

Example 1

Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: The longest subarray is [2,4] or [4,7].

Example 2

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The longest subarray is [2,4,7,2].

Example 3

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3
Explanation: The longest subarray of equal values is length 3 (three 2's).

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

Approach

We need the longest window [l..r] where max(nums[l..r]) - min(nums[l..r]) <= limit.

Two common sliding-window techniques:

  1. Multiset (or balanced BST) to maintain current window’s min and max. Expand right pointer; when condition violated, shrink left pointer and erase from multiset. Time: O(n log n), Space: O(n).

  2. Monotonic deques (optimal): maintain two deques:

    • decrease keeps current window’s values in decreasing order (front = max)
    • increase keeps values in increasing order (front = min) Push new value by popping from back while invariant violated. When shrinking left, pop from front if it equals outgoing value. This yields O(n) time and O(n) space.

Solutions

Multiset (balanced BST) — O(n log n)

class Solution:
def longestSubarray(self, nums, limit):
    multiset<int> ms
    left = 0, rtn = 0
    for (right = 0 right < (int)len(nums) right += 1) :
    ms.insert(nums[right])
    while *ms.rbegin() - *ms.begin() > limit:
        ms.erase(ms.find(nums[left]))
        left += 1
    rtn = max(rtn, right - left + 1)
return rtn

Monotonic Deques — O(n)

class Solution:
def longestSubarray(self, nums, limit):
    deque<int> increase, decrease # store values (or indices)
    left = 0, rtn = 0
    for (right = 0 right < (int)len(nums) right += 1) :
    val = nums[right]
    # maintain increasing deque for min
    while not not increase  and  increase[-1] > val) increase.pop(:
    increase.append(val)
    # maintain decreasing deque for max
    while not not decrease  and  decrease[-1] < val) decrease.pop(:
    decrease.append(val)
    # shrink window while invalid
    while decrease[0] - increase[0] > limit:
        if nums[left] == decrease[0]) decrease.pop_front(:
        if nums[left] == increase[0]) increase.pop_front(:
        left += 1
    rtn = max(rtn, right - left + 1)
return rtn

Complexity

  • Time: O(n) with monotonic deques, O(n log n) with multiset.
  • Space: O(n).

Template Reference