1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

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:

1. Initialize two deques (maxN and minN) to keep track of maximum and minimum elements in the current window.
2. Initialize variables l and r to represent the left and right pointers of the window, respectively.
3. Iterate over each element in nums using the index r: - Update maxN and minN 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, increment l 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.
4. Return res, which holds the size of the longest subarray with elements having an absolute difference less than or equal to limit.

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;
};