DSA problem
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit. The absolute difference between any two elements is equivalent to the difference between the max and the min of the subarray.
The key observation is that the validity predicate "max - min <= limit" is monotone: if a window is valid, every sub-window inside it is too. That makes this problem a classic two-pointer sliding-window candidate. The remaining engineering challenge is efficiently tracking the running max and min as the window slides.
The textbook solution uses two monotonic deques. A max-deque stores indices whose values decrease monotonically from front to back (front = max), and a min-deque stores indices whose values increase monotonically from front to back (front = min). Each deque supports amortized O(1) update because every index is pushed and popped at most once.
The algorithm walks a right pointer through the array, pushing each new index into both deques while preserving their monotone shapes. Whenever nums[max_dq.front] - nums[min_dq.front] > limit, we advance the left pointer and drop any front index that falls out of the window. After each step the window [left, right] is valid, so we track right - left + 1 as a candidate for the answer. The total work is O(n) time and O(n) space.
Examples
nums = [8,2,4,7], limit = 42nums = [10,1,2,4,7,2], limit = 54nums = [4,2,2,2,4,4,2,2], limit = 03Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 0 <= limit <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.