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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Thinking Process

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.
Sliding window a b c d e window expand right, shrink left when invalid

Solutions

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

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> ms;
        int left = 0, rtn = 0;
        for (int right = 0; right < (int)nums.size(); right++) {
            ms.insert(nums[right]);
            while (*ms.rbegin() - *ms.begin() > limit) {
                ms.erase(ms.find(nums[left]));
                left++;
            }
            rtn = max(rtn, right - left + 1);
        }
        return rtn;
    }
};

Solution Explanation

Approach: Fixed-size window (this problem)

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

How the code works:

  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)

      Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Pattern: Fixed-size window (this problem)
  • decrease keeps current window’s values in decreasing order (front = max)
  • increase keeps values in increasing order (front = min)

References

Template Reference