Longest Continuous Subarray with Absolute Diff Less Than or Equal to Limit
Problem Statement
Given an integer array nums and an integer limit, return the size of the longest non-empty contiguous subarray such that the absolute difference between any two elements in that subarray is less than or equal to limit.
Input
An integer array nums and an integer limit that bounds the allowed difference between the window maximum and minimum.
Output
An integer: the maximum length of a contiguous subarray whose largest and smallest values differ by at most limit.
Constraints
- •
1 <= nums.length <= 10^5 - •
1 <= nums[i] <= 10^9 - •
0 <= limit <= 10^9
Examples
Example 1
nums = [8,2,4,7], limit = 4
2Example 2
nums = [10,1,2,4,7,2], limit = 5
4Example 3
nums = [4,2,2,2,4,4,2,2], limit = 0
3Learning Objectives
- Recognise that checking every pair is unnecessary because only the window maximum and minimum matter.
- Maintain two monotonic deques to read max and min in constant amortized time.
- Shrink the left boundary only while the current window violates **max - min <= limit**.
- Explain why a variable window remains valid after removing enough leftmost elements.
Intuition
The phrase absolute difference between any two elements sounds like many pairwise checks, but inside a window the worst pair is always the maximum and the minimum. Therefore the validity test is just current max - current min <= limit.
This is a variable-size sliding window: expand right to search for longer answers, and shrink left only when the max-min range becomes too large. The hard part is maintaining both extremes while values enter and leave. A decreasing deque gives the maximum, and an increasing deque gives the minimum. Together they make each validity check constant amortized time.
Common mistakes
- ×Checking adjacent differences instead of the difference between the window maximum and minimum.
- ×Using only one deque and losing the opposite extreme needed for the validity test.
- ×Shrinking the window once when invalid instead of continuing until **max - min <= limit** again.
- ×Removing deque fronts by value rather than by index, which breaks when duplicate values appear.
Algorithm Explanation
Window setup
Maintain left, a decreasing max-deque of indices, and an increasing min-deque of indices. The max-deque front points to the largest value in the current window. The min-deque front points to the smallest value. The window is valid exactly when their value difference is at most limit.
Window visualization
For nums = [10,1,2,4,7,2] and limit = 5, index 0 gives max 10 and min 10. Adding 1 makes the range 9, so the window is invalid and left moves past 10. The window grows through [1,2,4] with range 3. Adding 7 gives [1,2,4,7] with range 6, so left moves past 1 and the valid window becomes [2,4,7]. Adding the final 2 keeps max 7 and min 2, producing [2,4,7,2] of length 4.
Algorithm
- Initialise left = 0, best = 0, and two empty deques of indices.
- For each right, insert it into the max-deque after removing smaller or equal values from the back.
- Insert it into the min-deque after removing larger or equal values from the back.
- While the current max minus current min exceeds limit, remove left from deque fronts if present, then increment left.
- Update best with the current valid window length right - left + 1.
- Return best.
Solutions
Solution: Two monotonic deques
Use one deque to summarize the maximum and another to summarize the minimum. The window may expand optimistically, but whenever the range exceeds limit, move left until both deques again describe a valid window.
Step-by-step
- Keep the max-deque decreasing by value, so its front is the maximum.
- Keep the min-deque increasing by value, so its front is the minimum.
- After inserting right, test the current range with the two deque fronts.
- If the range is too large, advance left and discard any deque front equal to the old left index.
- Once valid, record the longest length seen.
O(n)
O(n)
Each index is pushed and popped from each deque at most once. In the worst case a deque can hold many window indices.
Java implementation
Dry Run
Sample input
nums = [10,1,2,4,7,2], limit = 5. Trace both deques as index:value pairs after inserting right and shrinking until the window is valid.
| right | nums[right] | left after shrink | max deque | min deque | best length |
|---|---|---|---|---|---|
| 0 | 10 | 0 | [0:10] | [0:10] | 1 |
| 1 | 1 | 1 | [1:1] | [1:1] | 1 |
| 2 | 2 | 1 | [2:2] | [1:1, 2:2] | 2 |
| 3 | 4 | 1 | [3:4] | [1:1, 2:2, 3:4] | 3 |
| 4 | 7 | 2 | [4:7] | [2:2, 3:4, 4:7] | 3 |
| 5 | 2 | 2 | [4:7, 5:2] | [5:2] | 4 |
The best valid window is [2,4,7,2] from indices 2 through 5. Its maximum is 7, its minimum is 2, and the difference is exactly 5.
Interview Tips
Reduce the condition to the extremes before discussing data structures. Interviewers want to hear that the pairwise absolute difference requirement is equivalent to bounding max - min. Then describe the two deque invariants. If asked for alternatives, a balanced tree or multiset also works in O(n log n), but the two-deque version is the linear sliding-window answer.
Likely follow-ups
- How would you return the actual subarray instead of only its length?
- How would the solution change if negative values were allowed?
- What if the limit changed for every right index?
- Can you solve it with a TreeMap, and what complexity would that have?
Similar Problems
Key Takeaways
- For any window, the largest absolute pair difference is **max - min**.
- Two monotonic deques maintain both extremes in linear time.
- Expand right first, then shrink left until the window becomes valid again.
- Duplicate values are safest when tracked by index, not by value alone.