Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is a medium arrays & hashing problem solved with the sliding window · variable pattern.
The best approach, optimal (sliding window + two monotonic deques), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
You are given an array of positive integers nums and an integer limit. Find the length of the longest contiguous subarray in which the absolute difference between any two elements is at most limit.
Since the largest difference inside a subarray is always its maximum minus its minimum, this is the same as asking for the longest subarray whose max - min <= limit. A single element always qualifies, so the answer is at least 1.
Examples
Example 1
- Input
nums = [3, 9, 7, 8, 10, 2], limit = 3- Output
4- Why
- [9, 7, 8, 10] has max 10 and min 7, a difference of 3. Any longer window would include 3 or 2 and break the limit.
Example 2
- Input
nums = [6, 6, 6, 1, 6], limit = 0- Output
3- Why
- With limit 0 every value in the window must be equal: the first three 6s.
Example 3
- Input
nums = [2, 11, 4], limit = 10- Output
3- Why
- The largest difference in the whole array is 11 - 2 = 9, which is within the limit.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Optimal (sliding window + two monotonic deques) | O(n) | O(n) |
1Brute force
O(n²)For each of n starts the inner loop can run to the end of the array.O(1)Only the running max, min and indices.Fix each start index and extend the window to the right while tracking its running max and min. Stop as soon as max - min exceeds the limit, because extending further can only make it worse.
- For each start i, set hi = lo = nums[i].
- For j from i to n - 1: update hi and lo with nums[j]; if hi - lo > limit, break; else best = max(best, j - i + 1).
- Return best.
class Solution {
public int longestSubarray(int[] nums, int limit) {
int n = nums.length, best = 0;
for (int i = 0; i < n; i++) {
int hi = nums[i], lo = nums[i];
for (int j = i; j < n; j++) {
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;
}
}class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
n = len(nums)
best = 0
for i in range(n):
hi = lo = nums[i]
for j in range(i, n):
hi = max(hi, nums[j])
lo = min(lo, nums[j])
if hi - lo > limit:
break
best = max(best, j - i + 1)
return bestclass Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size(), best = 0;
for (int i = 0; i < n; i++) {
int hi = nums[i], lo = nums[i];
for (int j = i; j < n; j++) {
hi = max(hi, nums[j]);
lo = min(lo, nums[j]);
if (hi - lo > limit) {
break;
}
best = max(best, j - i + 1);
}
}
return best;
}
};function longestSubarray(nums, limit) {
const n = nums.length;
let best = 0;
for (let i = 0; i < n; i++) {
let hi = nums[i], lo = nums[i];
for (let j = i; j < n; j++) {
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;
}2Optimal (sliding window + two monotonic deques)
O(n)Each index is pushed into and popped from each deque at most once, and left only moves forward.O(n)The deques can hold up to n indices (for example, on a strictly increasing array the min deque keeps everything).Slide a window [left, right]. Keep a deque of indices whose values are decreasing (its front is the window max) and another whose values are increasing (its front is the window min). When a new element arrives, pop from the back of each deque every index it dominates, then push it. While max - min exceeds the limit, move left forward and drop deque fronts that fell out of the window. Each window that survives is valid, so record its length.
- left = 0, best = 0; maxQ and minQ are empty deques of indices.
- For each right: pop from maxQ's back while its value < nums[right], then push right; pop from minQ's back while its value > nums[right], then push right.
- While nums[maxQ.front] - nums[minQ.front] > limit: left++, and pop each deque's front if it is now < left.
- best = max(best, right - left + 1). Return best.
class Solution {
public int longestSubarray(int[] nums, int limit) {
Deque<Integer> maxQ = new ArrayDeque<>(); // values decreasing
Deque<Integer> minQ = new ArrayDeque<>(); // values increasing
int left = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
while (!maxQ.isEmpty() && nums[maxQ.peekLast()] < nums[right]) maxQ.pollLast();
maxQ.addLast(right);
while (!minQ.isEmpty() && nums[minQ.peekLast()] > nums[right]) minQ.pollLast();
minQ.addLast(right);
while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > limit) {
left++;
if (maxQ.peekFirst() < left) maxQ.pollFirst();
if (minQ.peekFirst() < left) minQ.pollFirst();
}
best = Math.max(best, right - left + 1);
}
return best;
}
}from collections import deque
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
max_q = deque() # indices, values decreasing
min_q = deque() # indices, values increasing
left = best = 0
for right, x in enumerate(nums):
while max_q and nums[max_q[-1]] < x:
max_q.pop()
max_q.append(right)
while min_q and nums[min_q[-1]] > x:
min_q.pop()
min_q.append(right)
while nums[max_q[0]] - nums[min_q[0]] > limit:
left += 1
if max_q[0] < left:
max_q.popleft()
if min_q[0] < left:
min_q.popleft()
best = max(best, right - left + 1)
return bestclass Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
deque<int> maxQ; // values decreasing
deque<int> minQ; // values increasing
int left = 0, best = 0;
for (int right = 0; right < (int)nums.size(); right++) {
while (!maxQ.empty() && nums[maxQ.back()] < nums[right]) maxQ.pop_back();
maxQ.push_back(right);
while (!minQ.empty() && nums[minQ.back()] > nums[right]) minQ.pop_back();
minQ.push_back(right);
while (nums[maxQ.front()] - nums[minQ.front()] > limit) {
left++;
if (maxQ.front() < left) maxQ.pop_front();
if (minQ.front() < left) minQ.pop_front();
}
best = max(best, right - left + 1);
}
return best;
}
};function longestSubarray(nums, limit) {
const maxQ = [], minQ = []; // index arrays used as deques
let maxHead = 0, minHead = 0;
let left = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
while (maxQ.length > maxHead && nums[maxQ[maxQ.length - 1]] < nums[right]) maxQ.pop();
maxQ.push(right);
while (minQ.length > minHead && nums[minQ[minQ.length - 1]] > nums[right]) minQ.pop();
minQ.push(right);
while (nums[maxQ[maxHead]] - nums[minQ[minHead]] > limit) {
left++;
if (maxQ[maxHead] < left) maxHead++;
if (minQ[minHead] < left) minHead++;
}
best = Math.max(best, right - left + 1);
}
return best;
}Edge cases to test
- A single element: the answer is 1
- limit = 0: the longest run of equal values
- A limit so large that the whole array qualifies
- Strictly increasing or decreasing input, where the oldest element is always the one to drop
Hints
Hint 1
A window is valid exactly when max(window) - min(window) <= limit. Every pair inside then also satisfies the limit.
Hint 2
If a window is invalid, every larger window containing it is invalid too, so a sliding window works: grow on the right, shrink on the left.
Hint 3
The hard part is the window's max and min as the left edge moves. Two monotonic deques (one decreasing, one increasing) give both in O(1).
FAQ
What is the best time complexity for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
Optimal (sliding window + two monotonic deques) runs in O(n) time and O(n) extra space. Each index is pushed into and popped from each deque at most once, and left only moves forward.
Which pattern does Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit use?
It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.
Is there a brute force solution for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
Yes. Brute force takes O(n²) time and O(1) space. Fix each start index and extend the window to the right while tracking its running max and min.
Which edge cases should I test for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
A single element: the answer is 1; limit = 0: the longest run of equal values; A limit so large that the whole array qualifies; Strictly increasing or decreasing input, where the oldest element is always the one to drop.