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

summary

• The problem is to find the size of the longest non-empty subarray in the given array of integers such that the absolute difference between any two elements of this subarray is less than or equal to the given limit.

approach

• The approach used is to use a sliding window technique with a multiset data structure to store the elements of the subarray
• The multiset is used to keep track of the minimum and maximum elements in the current subarray
• The sliding window is expanded to the right by adding elements to the multiset and contracting the window from the left by removing elements from the multiset if the absolute difference between the minimum and maximum elements exceeds the limit.

complexity

• O(N log N) due to the insertion and removal operations in the multiset, where N is the size of the input array.

explain

• The solution code initializes two pointers, l and r, to the start of the array
• It also initializes a multiset, multi, to store the elements of the subarray
• The code then enters a loop where it expands the sliding window to the right by adding elements to the multiset and checking if the absolute difference between the minimum and maximum elements exceeds the limit
• If it does, the code contracts the window from the left by removing elements from the multiset
• The code keeps track of the maximum length of the subarray seen so far and returns it at the end.

Solution Code:

class Solution {
public:
    int longestSubarray(vector& nums, int limit) {
        int l = 0;
        int r = 0;
        multiset multi;
        int N = nums.size();
        int ans = 0;
        
        multi.insert(nums[0]);
        while(r < N){
            int last = *(multi.rbegin());
            int first = *(multi.begin());
            if (abs(last - first) <= limit){
                ans = max(ans, r-l+1);
                r++;
                if (r < N){
                    multi.insert(nums[r]);
                }
            } else{
                multi.erase(multi.find(nums[l]));
                l++;
            }
        }
        return ans;
    }
};