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

MediumProblemExternal linkUpdated Oct 31, 2026

Description

Given an array of integers nums and an integer limit, return the length of the longest non-empty subarray in which the absolute difference between any two elements is at most limit.

Any two elements of a subarray differ by at most its maximum minus its minimum, so the condition is the same as: maximum − minimum ≤ limit.

Examples

Example 1

Input: nums = [8, 2, 4, 7], limit = 4

Output: 2

Explanation: [2, 4] has a difference of 2, within 4, and so does [4, 7]; every longer subarray holds a pair further apart (8 and 2, 2 and 7), so the answer is 2.

Example 2

Input: nums = [10, 1, 2, 4, 7, 2], limit = 5

Output: 4

Explanation: [2, 4, 7, 2] spans 7 − 2 = 5, within the limit: length 4.

Example 3

Input: nums = [4, 2, 2, 2, 4, 4, 2, 2], limit = 0

Output: 3

Explanation: A limit of 0 needs equal values: the three 2s in a row.

Constraints

1 ≤ nums.length ≤ 10^5
1 ≤ nums[i] ≤ 10^9
0 ≤ limit ≤ 10^9

Editorial

Brute Force

Intuition

Try every start i. Grow the subarray to the right one value at a time, keeping its running maximum and minimum. As soon as maximum − minimum passes limit, no longer subarray from i can work, so stop and try the next start. The longest one that worked is the answer.

Step-by-Step Explanation

Let's trace nums = [10, 1, 2, 4, 7, 2], limit = 5:

Start at index 0: the window reaches index 0 (max 10, min 10). Adding 1 would span 9. Longest so far 1.
Start at index 1: the window reaches index 3 (max 4, min 1). Adding 7 would span 6. Longest so far 3.
Start at index 2: the window reaches index 5 (max 7, min 2). Longest so far 4.
Start at index 3: the window reaches index 5 (max 7, min 2). Longest so far 4.
Start at index 4: the window reaches index 5 (max 7, min 2). Longest so far 4.
Start at index 5: the window reaches index 5 (max 2, min 2). Longest so far 4.

Grow Every Start — Each step shows the longest window from one start.

Algorithm

For each start i, set hi = lo = nums[i].
For j from i on: update hi and lo with nums[j]; if hi - lo > limit, stop; otherwise record j - i + 1.
Return the longest length recorded.

Code

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int best = 0;
        for (int i = 0; i < (int)nums.size(); i++) {       // every start
            int hi = nums[i], lo = nums[i];
            for (int j = i; j < (int)nums.size(); j++) {   // grow it while the span fits
                hi = max(hi, nums[j]);
                lo = min(lo, nums[j]);
                if (hi - lo > limit) break;
                best = max(best, j - i + 1);
            }
        }
        return best;
    }
};

class Solution:
    def longestSubarray(self, nums: list[int], limit: int) -> int:
        best = 0
        for i in range(len(nums)):               # every start
            hi = lo = nums[i]
            for j in range(i, len(nums)):        # grow it while the span fits
                hi, lo = max(hi, nums[j]), min(lo, nums[j])
                if hi - lo > limit:
                    break
                best = max(best, j - i + 1)
        return best

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int best = 0;
        for (int i = 0; i < nums.length; i++) {                // every start
            int hi = nums[i], lo = nums[i];
            for (int j = i; j < nums.length; j++) {            // grow it while the span fits
                hi = Math.max(hi, nums[j]);
                lo = Math.min(lo, nums[j]);
                if (hi - lo > limit) break;
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

var longestSubarray = function(nums, limit) {
    let best = 0;
    for (let i = 0; i < nums.length; i++) {      // every start
        let hi = nums[i], lo = nums[i];
        for (let j = i; j < nums.length; j++) {  // grow it while the span fits
            hi = Math.max(hi, nums[j]);
            lo = Math.min(lo, nums[j]);
            if (hi - lo > limit) break;
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
};

Complexity Analysis

Time Complexity: O(n²)

When the limit is generous, every start grows to the end of the array.

Space Complexity: O(1)

A few numbers.

Why This Approach Is Not Efficient

With 10^5 values that all fit the limit, every start grows to the end: about 5 × 10^9 steps, over the time limit in Python and JavaScript. The starts overlap, and each one reads values the start before it just read.

Slide one window instead. Move the right edge one step at a time; when the window gets too wide, move the left edge until it fits again. Both edges only move forward, so that's O(n) moves. What's left is knowing the window's maximum and minimum as both edges move. A sorted structure or two heaps would give them in O(log n) per step. Two monotonic deques give them in O(1) on average: one keeps the maximum at its front, the other the minimum.

Optimal Approach - Two Monotonic Deques

Intuition

Keep two deques of indexes. In hi, the values fall from front to back, so hi[0] is the window's maximum: a new value pops every value no bigger than itself off the back first, because a smaller value with a bigger one after it can never be the maximum again. In lo, the values rise, so lo[0] is the minimum, with the comparison flipped.

For each new right: push it into both deques. While the maximum minus the minimum is more than limit, move left forward, and drop each deque's front if its index has fallen behind left. The window [left, right] then fits, so record its length.

Step-by-Step Explanation

Let's trace nums = [10, 1, 2, 4, 7, 2], limit = 5:

10 joins both deques. The span is 0, so the window holds 1.
1 joins both deques, knocking 10 off the min deque. The span is 9, too wide, so the left edge moves to index 1; the window holds 1.
2 joins both deques, knocking 1 off the max deque. The span is 1, so the window holds 2.
4 joins both deques, knocking 2 off the max deque. The span is 3, so the window holds 3.
7 joins both deques, knocking 4 off the max deque. The span is 6, too wide, so the left edge moves to index 2; the window holds 3.
2 joins both deques, knocking 7, 4 and 2 off the min deque. The span is 5, so the window holds 4.

Two Deques, One Window — Amber is the window's maximum, teal its minimum; the deques below hold the candidates.

Algorithm

Start with two empty deques, left = 0 and best = 0.
For each right: pop hi's back while it's ≤ nums[right], and lo's back while it's ≥ nums[right]; push right into both.
While nums[hi[0]] - nums[lo[0]] > limit: left += 1, and pop each front whose index is < left.
best = max(best, right - left + 1). Return best.

Code

JavaScript keeps each deque in an array with a head and a tail index: every index is pushed once, so n slots are enough.

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> hi, lo;                   // indexes: hi's values fall (front = max), lo's rise (front = min)
        int left = 0, best = 0;
        for (int right = 0; right < (int)nums.size(); right++) {
            while (!hi.empty() && nums[hi.back()] <= nums[right]) hi.pop_back();
            while (!lo.empty() && nums[lo.back()] >= nums[right]) lo.pop_back();
            hi.push_back(right);
            lo.push_back(right);
            while (nums[hi.front()] - nums[lo.front()] > limit) {
                left++;                      // too wide: move the left edge
                if (hi.front() < left) hi.pop_front();
                if (lo.front() < left) lo.pop_front();
            }
            best = max(best, right - left + 1);
        }
        return best;
    }
};

from collections import deque

class Solution:
    def longestSubarray(self, nums: list[int], limit: int) -> int:
        hi = deque()                         # indexes, values falling: hi[0] is the window's max
        lo = deque()                         # indexes, values rising: lo[0] is the window's min
        left = best = 0
        for right, x in enumerate(nums):
            while hi and nums[hi[-1]] <= x:
                hi.pop()
            while lo and nums[lo[-1]] >= x:
                lo.pop()
            hi.append(right)
            lo.append(right)
            while nums[hi[0]] - nums[lo[0]] > limit:
                left += 1                    # too wide: move the left edge
                if hi[0] < left:
                    hi.popleft()
                if lo[0] < left:
                    lo.popleft()
            best = max(best, right - left + 1)
        return best

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> hi = new ArrayDeque<>();   // indexes, values falling: the front is the max
        Deque<Integer> lo = new ArrayDeque<>();   // indexes, values rising: the front is the min
        int left = 0, best = 0;
        for (int right = 0; right < nums.length; right++) {
            while (!hi.isEmpty() && nums[hi.peekLast()] <= nums[right]) hi.pollLast();
            while (!lo.isEmpty() && nums[lo.peekLast()] >= nums[right]) lo.pollLast();
            hi.offerLast(right);
            lo.offerLast(right);
            while (nums[hi.peekFirst()] - nums[lo.peekFirst()] > limit) {
                left++;                           // too wide: move the left edge
                if (hi.peekFirst() < left) hi.pollFirst();
                if (lo.peekFirst() < left) lo.pollFirst();
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

var longestSubarray = function(nums, limit) {
    const hi = new Int32Array(nums.length);   // indexes, values falling: hi[hh] is the max
    const lo = new Int32Array(nums.length);   // indexes, values rising: lo[lh] is the min
    let hh = 0, ht = 0, lh = 0, lt = 0;
    let left = 0, best = 0;
    for (let right = 0; right < nums.length; right++) {
        while (ht > hh && nums[hi[ht - 1]] <= nums[right]) ht--;
        while (lt > lh && nums[lo[lt - 1]] >= nums[right]) lt--;
        hi[ht++] = right;
        lo[lt++] = right;
        while (nums[hi[hh]] - nums[lo[lh]] > limit) {
            left++;                           // too wide: move the left edge
            if (hi[hh] < left) hh++;
            if (lo[lh] < left) lh++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
};

Complexity Analysis

Time Complexity: O(n)

Each index is pushed into each deque once and popped at most once, and left only moves forward.

Space Complexity: O(n)

The two deques; on sorted input one of them holds the whole window.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Shrinking when the span equals the limit. while nums[hi[0]] - nums[lo[0]] >= limit:

On nums = [10, 1, 2, 4, 7, 2], limit = 5 it returns 3; the answer is 4. The difference may be equal to limit: shrink only while it's greater, > limit.

Dropping a front at the new left edge. if hi[0] <= left:

On nums = [8, 2, 4, 7], limit = 4 it crashes with IndexError: deque index out of range; the answer is 2. After left moves, the window starts at index left, so a front at left is still inside. Drop only a front that fell behind it: < left.

Keeping values and dropping them by value. if hi[0] == nums[left]:

On nums = [1, 6, 6, 1, 6], limit = 4 it crashes with IndexError: deque index out of range; the answer is 2. Popping equal values from the back keeps one copy of a repeated maximum. When the left edge passes an older copy, comparing by value drops the newer one, still inside the window. Store indexes.

Where This Pattern Is Taught

This problem practises two monotonic deques on a variable window. It's taught in Monotonic Deque: the Window's Maximum, where the same two deques are stepped through on this example.