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

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.

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.

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

---

This question is asking us the largest continuous subarray where its maximum value subtracted by its minimum value is less than or equal to the limit range.

If we're looking for any continuous subarray or substring that satisfies a specific constraint, that is typically an indication that a sliding window can be applied.

What we could do is utilize a hashmap to track the values within our window which would be the distance between the left and right pointer that we'd create.  We'd calculate the difference between the maximum number and the minimum value within our window, and it was over the limit, we'd evict the leftmost number.

However, that would require quadratic time to calculate the maximum and minimum value within each iteration.

Our first thought may be to calculate the mean and maximum value each time we insert a number into our window, but if we were to evict that same number from the left side of the window later, then that mean or maximum value would remain for a number that doesn't exist within the window anymore. 

From the problem Sliding Window Maximum, we learned that Monotonic Queues are excellent for tracking the maximum or minimum value within a window.  The reason for this is if we evict the current maximum or minimum from the window, we will have the second-most maximum or minimum immediately and won't have to recalculate it.

To solve this problem, we will utilize two Monotonic Queues, one for the current maximum within the window and one for the current minimum.  

This will allow us to access the current maximum and minimum in constant time, and will also give us the second-most maximum or minimum once a number from the window.

---

Let's start by creating a left and a right pointer to signify the bounds of our sliding window.

        left, right = 0, 0

 

We'll also create a maximum and minimum window queue.

        min_window = collections.deque()
        max_window = collections.deque()

 

Next, we'll need a running counter to track the longest windows we encounter.

        longest = 0

 

While the right pointer hasn't passed the end of the input array, we are still considering values for our window.

        while right < len(nums):

 

Starting off, we will see if the current number at the right pointer is greater than the rightmost value in the maximum queue.

We'll make a loop to pop each smaller value from the queue.

Since we are considering this value for the current window, there is no point in ever considering any lesser value as the sliding window maximum.  This is also good because if there is a greater value than the current number, it won't be popped out and the current number will act as a backup plan in the scenario that we evict the greater value from the window later.

            while max_window and nums[right] > max_window[-1]:
                max_window.pop()

 

Once we have popped each smaller value from the maximum queue, we will append the current number at the right pointer.

            max_window.append(nums[right])

 

Next, we'll do the same thing for the minimum queue, but popping values less than the current number.

            while min_window and nums[right] < min_window[-1]:
                min_window.pop()
            min_window.append(nums[right])

 

Once we have appended the current number to each queue, we will expand our window.

            right += 1

 

Similar to other sliding window problems, we will expand until our window no longer satisfies the given constraint.  In this case, when the maximum and minimum number within the window have an absolute difference greater than the limit.

            while max_window[0] - min_window[0] > limit:

 

When that happens, we will need to shrink the window by evicting the leftmost position.  This will continue until our window is valid again.

To evict the leftmost position here, we will just look at which leftmost value from each queue is the number at the left pointer and pop it out.

                if max_window[0] == nums[left]:
                    max_window.popleft()
                if min_window[0] == nums[left]:
                    min_window.popleft()

 

After, we'll increment the left pointer.

                left += 1

 

Once we have broken from the loop, our window is valid again so we will test it for the longest window so far.

            longest = max(longest, right - left)

 

After we have traversed the entire array, we will return the longest window we encountered.

        return longest

---