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

Intuition

To solve this problem, we can use a sliding window approach and keep track of the minimum and maximum elements within the current window.

Approach 1: Sliding Window + Binary Search Tree

This approach utilizes a sliding window in combination with a balanced binary search tree implemented via std::multiset in C++. The multiset allows for efficient insertion, deletion, and access to the smallest and largest elements, making it a suitable data structure for this problem.

Explanation:

1. Initialization:
2. Initialize res to store the result (length of the longest subarray).
3. left is initialized to 0 to denote the starting index of the sliding window.
4. A multiset called ms is used to maintain the elements within the current window.
5. Expanding the Window:
6. Iterate through the array using a right pointer to expand the window.
7. Insert the current element nums[right] into the multiset.
8. Maintaining the Condition:
9. After inserting a new element, check if the current window satisfies the condition: the difference between the maximum and minimum elements in the window should be less than or equal to limit.
10. In multiset, the smallest element can be accessed using *ms.begin() and the largest element using *ms.rbegin().
11. If the difference between these elements exceeds limit, shrink the window from the left by removing nums[left] from the multiset and incrementing the left pointer.
12. Updating the Result:
13. Update res with the size of the current valid window, which is right - left + 1.
14. Return the Result:
15. After iterating through the array, res will contain the length of the longest subarray that satisfies the condition.

Complexity

• Time complexity: O(n*log(n))
• Space complexity: O(n)

Code

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int res = 0, left = 0;
        multiset<int> ms;

        for (int right = 0; right < (int)nums.size(); right++) {
            ms.insert(nums[right]);

            while (*ms.rbegin() - *ms.begin() > limit) {
                ms.erase(ms.find(nums[left++]));
            }

            res = max(res, right - left + 1);
        }

        return res;
    }
};

Approach 2: Sliding Window + Monotonic Queue

This optimized solution uses a sliding window in combination with two monotonic queues to efficiently maintain the minimum and maximum values within the current window. This approach ensures that the operations of inserting, removing, and accessing the minimum and maximum values are all handled in constant time, making it more efficient than using a binary search tree.

Explanation:

1. Initialization:
2. Initialize res to store the result (length of the longest subarray).
3. left is initialized to 0 to denote the starting index of the sliding window.
4. Two deques, minDq and maxDq, are used to maintain elements in the current window in increasing and decreasing order, respectively.
5. Expanding the Window:
6. Iterate through the array using a right pointer to expand the window.
7. Update minDq to maintain the minimum elements: remove elements from the back of minDq while the current element is smaller than the elements at the back.
8. Update maxDq to maintain the maximum elements: remove elements from the back of maxDq while the current element is larger than the elements at the back.
9. Insert the current element into both minDq and maxDq.
10. Maintaining the Condition:
11. Check if the current window satisfies the condition: the difference between the maximum and minimum elements should be less than or equal to limit.
12. The minimum element can be accessed using minDq.front() and the maximum element using maxDq.front().
13. If the condition is violated, shrink the window from the left by removing the elements at left from the deques and incrementing the left pointer.
14. Updating the Result:
15. Update res with the size of the current valid window, which is right - left + 1.
16. Return the Result:
17. After iterating through the array, res will contain the length of the longest subarray that satisfies the condition.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Code

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int res = 0, left = 0;

        deque<int> minDq, maxDq;

        for (int right = 0; right < (int)nums.size(); right++) {
            while (!minDq.empty() && nums[right] < minDq.back()) {
                minDq.pop_back();
            }

            while (!maxDq.empty() && nums[right] > maxDq.back()) {
                maxDq.pop_back();
            }

            minDq.push_back(nums[right]);
            maxDq.push_back(nums[right]);

            while (maxDq.front() - minDq.front() > limit) {
                if (minDq.front() == nums[left]) minDq.pop_front();
                if (maxDq.front() == nums[left]) maxDq.pop_front();
                ++left;
            }

            res = max(res, right - left + 1);
        }

        return res;
    }
};