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

MediumSliding Window · Monotonic Deque🧩 Queue & Monotonic Deque LeetCode #1438 ↗Updated Oct 30, 2026

Problem

Given an integer array nums and an integer limit, find the length of the longest non-empty contiguous subarray in which the difference between any two elements is at most limit. Equivalently, the subarray's max - min must not exceed limit.

Inputnums = [8,2,4,7], limit = 4Output2 ([2,4] or [4,7])

Inputnums = [10,1,2,4,7,2], limit = 5Output4 ([2,4,7,2])

Inputnums = [4,2,2,2,4,4,2,2], limit = 0Output3

1 ≤ n ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹ · 0 ≤ limit ≤ 10⁹

Try it yourself

Java

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Only the window's max and min matter, and if a window is valid so is every window inside it — so a sliding window works. Two monotonic deques report the current max and min in O(1) as the window slides.

PatternQueue & Monotonic Deque

Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.

Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.

Open the Queue & Monotonic Deque guide →

Approaches

Brute ForceGrow From Every Start

Time O(n²)Space O(1)

Fix a left end and extend right, updating the running min and max. As soon as max - min exceeds limit, any longer extension is also invalid, so stop and move to the next start.

Java

public int longestSubarray(int[] nums, int limit) {
    int n = nums.length;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int lo = nums[i], hi = nums[i];
        for (int j = i; j < n; j++) {
            lo = Math.min(lo, nums[j]);
            hi = Math.max(hi, nums[j]);
            if (hi - lo > limit) break; // longer windows only get worse
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Easy and correct, but quadratic when most windows stay valid.

BetterSliding Window + Sorted Multiset (TreeMap)

Time O(n log n)Space O(n)

Slide a window [left, right] and keep its values with counts in a TreeMap, so firstKey()/lastKey() give min and max. While the spread is too big, remove nums[left] and advance left.

Java

public int longestSubarray(int[] nums, int limit) {
    TreeMap<Integer, Integer> window = new TreeMap<>(); // value -> count
    int left = 0, best = 0;
    for (int right = 0; right < nums.length; right++) {
        window.merge(nums[right], 1, Integer::sum);
        while (window.lastKey() - window.firstKey() > limit) {
            if (window.merge(nums[left], -1, Integer::sum) == 0) window.remove(nums[left]);
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Linear number of window moves, but each costs a log factor.

OptimalSliding Window + Two Monotonic Deques

Time O(n)Space O(n)

maxDq keeps indices with decreasing values, minDq with increasing values; their fronts are the window max and min. A new element evicts back entries it dominates. When the spread is too big, move left and drop fronts that fell out of the window.

Java

public int longestSubarray(int[] nums, int limit) {
    Deque<Integer> maxDq = new ArrayDeque<>(); // indices, values decreasing
    Deque<Integer> minDq = new ArrayDeque<>(); // indices, values increasing
    int left = 0, best = 0;
    for (int right = 0; right < nums.length; right++) {
        while (!maxDq.isEmpty() && nums[maxDq.peekLast()] <= nums[right]) maxDq.pollLast();
        while (!minDq.isEmpty() && nums[minDq.peekLast()] >= nums[right]) minDq.pollLast();
        maxDq.offerLast(right);
        minDq.offerLast(right);
        while (nums[maxDq.peekFirst()] - nums[minDq.peekFirst()] > limit) {
            left++;
            if (maxDq.peekFirst() < left) maxDq.pollFirst();
            if (minDq.peekFirst() < left) minDq.pollFirst();
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry runnums = [8,2,4,7], limit = 4

L leftR right changed

R=0
8
L R
2

4

7

max 8, min 8, best=1
R=1
8
L
2
R
4

7

8-2=6 > 4 → shrink
R=1
8

2
L R
4

7

drop 8, best=1
R=2
8

2
L
4
R
7

4-2=2, best=2
R=3
8

2
L
4

7
R
7-2=5 > 4 → shrink
R=3
8

2

4
L
7
R
7-4=3, best=2 ✔

Every index enters and leaves each deque once — linear time.

Pro tip

Store indices, not values: that's how you know whether a front entry is still inside the window, even with duplicates.

At a glance

Level	Approach	Time	Space
Brute Force	Grow From Every Start	`O(n²)`	`O(1)`
Better	Sliding Window + Sorted Multiset (TreeMap)	`O(n log n)`	`O(n)`
Optimal	Sliding Window + Two Monotonic Deques	`O(n)`	`O(n)`

Common pitfalls

Checking only neighbouring elements — the condition is on the whole window's max and min.
Removing a value from the TreeMap without decrementing counts first — breaks duplicates.
Popping the deque fronts by value instead of by index, which mishandles repeated numbers.

Interview tips

Restate “all pairs within limit” as max - min ≤ limit immediately.
Justify the sliding window: a valid window stays valid when shrunk.
Offer the TreeMap version first if the deque details feel risky, then optimise.

Pattern

Sliding window + monotonic deque → longest window whose max/min must satisfy a bound.

My notes saved in this browser