← DSA Atlas
Dedicated problem page · #1438

Longest Continuous Subarray With Absolute Diff ≤ Limit

MediumSliding WindowLongest window with bounded max-min spreadSliding window with two monotonic deques
Solve on LeetCode ↗
1438
MediumSliding WindowSliding window with two monotonic dequesLongest window with bounded max-min spread

Longest Continuous Subarray With Absolute Diff ≤ Limit

Given an integer array nums and an integer limit, return the size of the longest contiguous subarray such that the absolute difference between any two of its elements is at most limit (equivalently, its max minus its min is at most limit).

Open official problem prompt ↗
In plain English

Find the longest contiguous slice whose largest and smallest elements differ by no more than limit.

Picture it like this

Picture a moving thermostat window: you slide a frame over daily temperatures and want the longest stretch where the hottest and coldest days differ by at most limit degrees. You keep two 'leaderboards' — one for the current hottest day, one for the coldest — and whenever the spread between the two leaders grows too big, you trim the oldest days off the back.

Example
Input
nums = [8,2,4,7], limit = 4
Output
2
Why
[2,4] has max-min = 2 <= 4 and [4,7] has spread 3 <= 4, but every length-3 window (e.g. [2,4,7], spread 5) exceeds the limit, so the longest valid length is 2.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
Pattern lesson

See the pattern, then code

Longest window with bounded max-min spread
Recognition clue

You want the LONGEST window whose validity depends on the current max and min simultaneously. Needing both extremes of a moving window in O(1) amortized is the signature of a monotonic-deque sliding window.

↗
Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Maintain the window max in a decreasing deque and the window min in an increasing deque, both storing indices. The fronts give the current max and min instantly. When their difference exceeds limit, advance left and pop any deque front that falls out of the window, until the spread is valid again.

New words, made simpleKnow these before the algorithm
Monotonic deque
A double-ended queue of indices kept in sorted value order so its front is always the current extreme (max or min) of the window.
Spread
max(window) - min(window); the window is valid exactly when spread <= limit.
Amortized O(1)
Each index is pushed and popped from each deque at most once, so per-step deque work averages to constant time.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force max/min per window

Recomputing extremes is wasteful; too slow for n up to 10^5.

For each start, extend end and recompute max and min each time.

Time O(n^2)Space O(1)
Two heaps / sorted structure

Works, but log factor and lazy-deletion bookkeeping are heavier than needed.

Keep window values in a balanced multiset or two heaps to query max and min.

Time O(n log n)Space O(n)
Best choiceTwo monotonic deques

Gives both extremes in O(1) with a single linear pass.

One decreasing deque for the max, one increasing deque for the min, both of indices.

Time O(n)Space O(n)
The rule we keep true

Invariant

max_dq is decreasing in value from front to back and min_dq is increasing, so nums[max_dq[0]] is the window maximum and nums[min_dq[0]] is the window minimum; after each iteration the window [left, right] has spread <= limit.

Why this is correct

Reasoning

A value that enters the window and is larger than earlier tail values can never again be beaten as the max while those older values remain, so popping the smaller tails loses nothing — the deque front stays the true max (symmetrically for the min deque). Because the fronts are the exact extremes, the shrink loop stops precisely when the window is valid, and each right endpoint is paired with the smallest feasible left, so the longest valid window is found. Every index enters and leaves each deque once, giving linear time.

The algorithm in three movesSay these aloud before coding
1Extend right; push its index onto a decreasing max-deque (popping smaller tail values) and an increasing min-deque (popping larger tail values)

right=1: maxDq front=8, minDq front=2, spread 6>4 -> left=1

2While nums[maxDeque front] - nums[minDeque front] > limit, advance left

right=2 (val 4): window [1..2], max=4 min=2 spread 2, len=2

3After advancing left, pop either deque's front if its index has fallen behind left

right=3 (val 7): spread 7-2=5>4 -> left=2, len=2

4Update the best length with right - left + 1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
80
21
42
73
1 · Readread 8
2 · Askupdate deques
3 · Update statemax_dq=[0], min_dq=[0], spread 0
4 · Resultbest=1
Key takeaway

The window [2,4] (indices 1-2) is a maximal run whose max-min spread stays within limit 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-7Set up deques and window

    max_dq and min_dq hold indices; left is the window start and best the answer.

  2. 2
    Lines 9-11Maintain the max deque

    Pop tail indices whose value is <= the incoming x, then append x's index so the deque stays decreasing and its front is the window max.

  3. 3
    Lines 12-14Maintain the min deque

    Symmetrically pop tail indices whose value is >= x so the deque stays increasing and its front is the window min.

  4. 4
    Lines 15-19Shrink on oversized spread

    While max minus min exceeds limit, advance left and evict any deque front whose index has dropped below left.

  5. 5
    Lines 20Record best length

    The window is now valid, so right - left + 1 is a candidate for the longest length.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • limit = 0: only runs of equal values qualify
  • Strictly increasing or decreasing array (each long window quickly violates the limit)
  • All elements equal (answer is n)
  • Single element (answer is 1)
  • Large values up to 10^9 — differences fit in Python ints with no overflow concern
!

Common beginner mistakes

  • Storing values instead of indices, which makes it impossible to know when a front has left the window
  • Using <= vs < inconsistently when popping tails — the max deque pops on <= x and the min deque pops on >= x to break ties by keeping the newer index
  • Popping the wrong deque's front, or forgetting to check both fronts against left after advancing
  • Using an if instead of a while for the shrink loop, which can leave the window invalid when the spread is exceeded by a large jump
Check your understanding

Why do the deques store indices rather than the element values themselves?

More in Sliding Window

#3Longest Substring Without Repeating CharactersVariable-size sliding window with last-seen index#424Longest Repeating Character ReplacementVariable-size window constrained by replaceable slots#76Minimum Window SubstringShrinkable window covering a multiset requirement#30Substring with Concatenation of All WordsWord-aligned sliding window over fixed-length tokens#121Best Time to Buy and Sell StockRunning minimum with best forward difference#209Minimum Size Subarray SumShrinking window on a sum threshold