1438. 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.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 0 <= limit <= 109

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int longest_length = 1;
        deque<int> min_queue;
        deque<int> max_queue;

        for (int left = 0, right = 0; right < nums.size(); ++right) {
            while (!min_queue.empty() && min_queue.back() > nums[right])
                min_queue.pop_back();
            min_queue.push_back(nums[right]);
            while (!max_queue.empty() && max_queue.back() < nums[right])
                max_queue.pop_back();
            max_queue.push_back(nums[right]);
            while (max_queue.front() - min_queue.front() > limit) {
                if (min_queue.front() == nums[left])
                    min_queue.pop_front();
                if (max_queue.front() == nums[left])
                    max_queue.pop_front();
                ++left;
            }
            longest_length = max(longest_length, right - left + 1);
        }

        return longest_length;
    }
};

from collections import deque
from typing import List

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        longest_length = 1
        min_queue = deque()
        max_queue = deque()

        left = 0
        for right in range(len(nums)):
            while min_queue and min_queue[-1] > nums[right]:
                min_queue.pop()
            min_queue.append(nums[right])
            while max_queue and max_queue[-1] < nums[right]:
                max_queue.pop()
            max_queue.append(nums[right])
            while max_queue[0] - min_queue[0] > limit:
                if min_queue[0] == nums[left]:
                    min_queue.popleft()
                if max_queue[0] == nums[left]:
                    max_queue.popleft()
                left += 1
            longest_length = max(longest_length, right - left + 1)

        return longest_length

Time Complexity:

• The time complexity of the longestSubarray function is $O(n)$, where $n$ is the length of the nums array.
• This is because each element is added and removed from the min_queue and max_queue at most once.
• The two while loops inside the for loop do not result in an overall quadratic complexity since the inner while loops are effectively controlled by the sliding window mechanism, making the algorithm linear.

Space Complexity:

• The space complexity of the longestSubarray function is $O(n)$ in the worst case, where $n$ is the length of the nums array.
• This is because, in the worst case, all elements could be added to both the min_queue and max_queue.
• However, typically the space used by the deques will be less than $O(n)$, depending on the distribution of elements in nums.