🎨Now live: Try our Free AI Image Generation Feature
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Dare2Solve
1 year ago

Intuition
The problem requires finding the longest subarray where the absolute difference between its elements does not exceed a given limit. To achieve this, we need an efficient way to manage and dynamically adjust the subarray as we iterate through the array nums
.
Approach
Sliding Window with Deques
We can use a sliding window approach with two deques to maintain the maximum and minimum elements within the current window:
- maxN: Stores pairs of (element, index) in non-increasing order.
- minN: Stores pairs of (element, index) in non-decreasing order.
Steps:
- Initialize two deques (
maxN
andminN
) to keep track of maximum and minimum elements in the current window. - Initialize variables
l
andr
to represent the left and right pointers of the window, respectively. - Iterate over each element in
nums
using the indexr
: - UpdatemaxN
andminN
by removing elements from the back that do not satisfy the current element's order requirements and then add the current element. - Check if the difference between the maximum and minimum elements in the current window (maxN[0] - minN[0] > limit
). If it exceeds the limit, incrementl
to reduce the window size until the condition is satisfied. - Calculate the size of the current valid subarray (r - l + 1
) and update the result (res
) with the maximum size encountered so far. - Return
res
, which holds the size of the longest subarray with elements having an absolute difference less than or equal tolimit
.
Edge Cases
- Handle arrays with single or few elements.
- Arrays where all elements already satisfy the condition from the start.
Complexity Analysis
- Time Complexity: O(n), where n is the number of elements in
nums
. Each element is added and removed from the deques at most once. - Space Complexity: O(n) due to the deques storing at most
n
elements in total, in the worst case.
This approach ensures that we efficiently find the longest subarray meeting the criteria using a linear pass with constant-time operations for maintaining the deques, making it suitable for large inputs.
Code
C++
class Solution {
public:
int longestSubarray(vector& nums, int limit) {
deque> minN;
deque> maxN;
int res = 0;
for (int l = 0, r = 0; r < nums.size(); ++r) {
while (!minN.empty() && minN.back().first >= nums[r]) minN.pop_back();
while (!maxN.empty() && maxN.back().first <= nums[r]) maxN.pop_back();
minN.push_back({nums[r], r});
maxN.push_back({nums[r], r});
while (maxN.front().first - minN.front().first > limit) {
l = min(maxN.front().second, minN.front().second) + 1;
if (maxN.front().second == l - 1) maxN.pop_front();
if (minN.front().second == l - 1) minN.pop_front();
}
res = max(res, r - l + 1);
}
return res;
}
};
Python
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
minN = deque()
maxN = deque()
res = 0
l = 0
for r in range(len(nums)):
while minN and minN[-1][0] >= nums[r]:
minN.pop()
while maxN and maxN[-1][0] <= nums[r]:
maxN.pop()
minN.append((nums[r], r))
maxN.append((nums[r], r))
while maxN and minN and maxN[0][0] - minN[0][0] > limit:
l = min(maxN[0][1], minN[0][1]) + 1
if maxN[0][1] == l - 1:
maxN.popleft()
if minN[0][1] == l - 1:
minN.popleft()
res = max(res, r - l + 1)
return res
Java
class Solution {
public int longestSubarray(int[] nums, int limit) {
Deque minN = new ArrayDeque<>();
Deque maxN = new ArrayDeque<>();
int res = 0;
for (int l = 0, r = 0; r < nums.length; ++r) {
while (!minN.isEmpty() && minN.peekLast()[0] >= nums[r]) {
minN.pollLast();
}
while (!maxN.isEmpty() && maxN.peekLast()[0] <= nums[r]) {
maxN.pollLast();
}
minN.offerLast(new int[]{nums[r], r});
maxN.offerLast(new int[]{nums[r], r});
while (maxN.peekFirst()[0] - minN.peekFirst()[0] > limit) {
l = Math.min(maxN.peekFirst()[1], minN.peekFirst()[1]) + 1;
if (maxN.peekFirst()[1] == l - 1) {
maxN.pollFirst();
}
if (minN.peekFirst()[1] == l - 1) {
minN.pollFirst();
}
}
res = Math.max(res, r - l + 1);
}
return res;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} limit
* @return {number}
*/
var longestSubarray = function (nums, limit) {
var minN = [];
var maxN = [];
var res = 0;
for (var l = 0, r = 0; r < nums.length; ++r) {
while (minN.length && minN[minN.length - 1][0] >= nums[r]) minN.pop();
while (maxN.length && maxN[maxN.length - 1][0] <= nums[r]) maxN.pop();
minN.push([nums[r], r]);
maxN.push([nums[r], r]);
while (maxN[0][0] - minN[0][0] > limit) {
l = Math.min(maxN[0][1], minN[0][1]) + 1;
if (maxN[0][1] === l - 1) maxN.shift();
if (minN[0][1] === l - 1) minN.shift();
}
res = Math.max(res, r - l + 1);
}
return res;
};