Get started

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Medium Problem & Solution

You are given an integer array nums and an integer limit. Find the length of the longest non-empty contiguous subarray in which the absolute difference…

Problem statement

You are given an integer array nums and an integer limit.

Find the length of the longest non-empty contiguous subarray in which the absolute difference between any two of its elements is at most limit. Equivalently, the subarray's largest value minus its smallest value must not exceed limit.

A single element always qualifies, so the answer is at least 1.

Example 1

Input: nums = [9,3,5,8], limit = 4
Output: 2
Explanation: `[3,5]` (difference 2) and `[5,8]` (difference 3) qualify; every window of length 3 has a spread above 4.

Example 2

Input: nums = [12,3,4,6,9,4], limit = 5
Output: 4
Explanation: `[4,6,9,4]` has maximum 9 and minimum 4, a spread of exactly 5.

Example 3

Input: nums = [5,3,3,3,5,5,3,3], limit = 0
Output: 3
Explanation: With `limit = 0` every element of the window must be equal; the longest run is `[3,3,3]`.

Constraints

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

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

Validity depends only on the window's extremes, and any sub-window of a valid window is valid. That monotonicity is exactly what a two-pointer sliding window needs; two monotonic deques supply the running max and min.

Approach

  1. Keep left = 0 and two deques of values: maxQ (non-increasing) and minQ (non-decreasing).
  2. For each right, pop from the back of maxQ every value smaller than nums[right], then push it; do the mirror image on minQ (pop values larger than it).
  3. While maxQ.front - minQ.front > limit, the window is too wide: if nums[left] is at the front of either deque, pop it from that front, then advance left.
  4. The window [left, right] is now valid; record right - left + 1 if it is the best so far.

Why it works

For a fixed right, the smallest valid left never moves backwards as right grows (adding an element can only widen the spread), so advancing left monotonically visits every candidate. Each deque holds the window's elements that could still become its max (or min); an element is dropped from the back only when a newer, larger (or smaller) element makes it irrelevant for every future window, so the fronts are always the true extremes.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Pop with a strict comparison (< for the max deque, > for the min deque) so equal values are kept; otherwise removing nums[left] by value can drop a duplicate that is still inside the window.
  • Shrink with a while, not an if — one new element can require several left moves.
  • A sorted multiset (or two heaps with lazy deletion) also works in O(n log n), but the deques are simpler and linear.

Reference solution

Python

from typing import List
from collections import deque

def longestSubarray(nums: List[int], limit: int) -> int:
    max_q = deque()
    min_q = deque()
    left = 0
    best = 0
    for right, v in enumerate(nums):
        while max_q and max_q[-1] < v:
            max_q.pop()
        max_q.append(v)
        while min_q and min_q[-1] > v:
            min_q.pop()
        min_q.append(v)
        while max_q[0] - min_q[0] > limit:
            if max_q[0] == nums[left]:
                max_q.popleft()
            if min_q[0] == nums[left]:
                min_q.popleft()
            left += 1
        best = max(best, right - left + 1)
    return best

JavaScript

var longestSubarray = function(nums, limit) {
    var n = nums.length;
    var maxQ = new Array(n), minQ = new Array(n);
    var maxH = 0, maxT = 0, minH = 0, minT = 0, left = 0, best = 0;
    for (var right = 0; right < n; right++) {
        var v = nums[right];
        while (maxT > maxH && maxQ[maxT - 1] < v) maxT--;
        maxQ[maxT++] = v;
        while (minT > minH && minQ[minT - 1] > v) minT--;
        minQ[minT++] = v;
        while (maxQ[maxH] - minQ[minH] > limit) {
            if (maxQ[maxH] === nums[left]) maxH++;
            if (minQ[minH] === nums[left]) minH++;
            left++;
        }
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Sliding Window Technique