Problem Statement

Given an integer array nums and an integer limit, return the maximum length of a continuous subarray such that the absolute difference between any two elements in this subarray is less than or equal to limit. The subarray must be non-empty.

Examples

Example 1:

• Input: nums = [1, 3, 6, 7, 9, 10], limit = 3
• Output: 3
• Explanation: Consider the [6, 7, 9] or [7, 9, 10] array. The absolute difference between any two elements in these subarrays is at most 3.

Example 2:

• Input: nums = [8, 2, 4, 10, 12], limit = 6
• Output: 3
• Explanation: The longest subarray is [8, 2, 4]. The absolute difference between any two elements in this subarray is at most 6.

Example 3:

• Input: nums = [1, 5, 9, 13, 14], limit = 4
• Output: 2
• Explanation: Consider the [1, 5], [5, 9], [9, 13] or [13, 14] array. The absolute difference between any two elements in these subarrays is at most 4.

Constraints:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁹
• 0 <= limit <= 10⁹

Solution

To solve this problem, we employ the Monotonic Queue technique to maintain two deques: one for tracking the maximum values and one for tracking the minimum values within the current window (subarray). The idea is to expand the window by moving the end pointer while checking if the difference between the maximum and minimum elements within this window exceeds the given limit. If it does, we shrink the window by moving the start pointer until the difference is within the limit. The length of the window is tracked to determine the maximum length of any valid subarray.

This approach works because the deques allow us to efficiently maintain and update the maximum and minimum values in the window, which enables us to check the conditions and adjust the window size in an optimal manner.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create two empty deques: maxDeque for storing indices of elements in decreasing order (to track the maximum values) and minDeque for storing indices in increasing order (to track the minimum values).
   • Initialize two integer variables, start and maxLength, to 0. start will represent the beginning of the current subarray, and maxLength will store the maximum length of the valid subarray found.

2. Iterate Through the Array:

   • Use a for-loop with end iterating from 0 to nums.length - 1. end represents the end of the current subarray.

3. Update maxDeque:

   • While maxDeque is not empty and the value at nums[end] is greater than or equal to the value at nums[maxDeque.peekLast()], remove the last element from maxDeque.
     Reason: We want to keep the largest element at the front of maxDeque.
   • Add the current index end to maxDeque.

4. Update minDeque:

   • While minDeque is not empty and the value at nums[end] is less than or equal to the value at nums[minDeque.peekLast()], remove the last element from minDeque.
     Reason: We want to keep the smallest element at the front of minDeque.
   • Add the current index end to minDeque.

5. Check the Condition:

   • While the difference between the values at nums[maxDeque.peekFirst()] and nums[minDeque.peekFirst()] is greater than limit, perform the following steps:
     • Increment the start pointer by 1 to shrink the window from the left.
     • If maxDeque.peekFirst() is less than start, remove the first element from maxDeque. Reason: We are no longer considering elements before the start index.
     • If minDeque.peekFirst() is less than start, remove the first element from minDeque. Reason: We are no longer considering elements before the start index.

6. Update Maximum Length:

   • Calculate the length of the current window as end - start + 1.
   • Update maxLength to be the maximum of its current value and the current window length.

7. Return Result:

   • After completing the loop, return maxLength, which contains the length of the longest subarray satisfying the condition.

Algorithm Walkthrough

Let's walk through the algorithm with the input nums = [1, 3, 6, 7, 9, 10] and limit = 3.