Problem Statement

You are given a 0-indexed array of integers called nums. A subarray of num is called continuous if the following condition is met:

• consider i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays within nums.

A subarray is defined as any contiguous, non-empty sequence of elements within an array.

Examples

Example 1:

• Input: nums = [1, 2, 2, 13, 1]
• Expected Output: 8
• Justification: The continuous subarrays are [1], [2], [2], [13], [1], [1, 2], [2, 2], and [1, 2, 2].

Example 2:

• Input: nums = [3, 3, 4, 2]
• Expected Output: 10
• Justification: The continuous subarrays are [3], [3], [4], [2], [3, 3], [3, 4], [4, 2], [3, 3, 4], [3, 4, 2], and [3, 3, 4, 2].

Example 3:

• Input: nums = [5, 17, 35, 26, 5]
• Expected Output: 5
• Justification: The continuous subarrays are [5], [17], [35], [26], and [5].

Constraints:

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

Solution

This problem is similar to the "Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit" problem, but with a twist. In this case, the limit is fixed at 2, meaning that we must find all subarrays where the maximum difference between any two elements does not exceed 2. The goal is to count the total number of such continuous subarrays within the given array.

To solve this problem, we use a sliding window approach combined with two deques (double-ended queues) to efficiently track the minimum and maximum values within the current subarray. The deques allow us to maintain the order of elements in a way that makes it easy to adjust the window size dynamically by moving the left pointer whenever the difference between the maximum and minimum values exceeds 2. By counting all valid subarrays ending at each position, we can calculate the total number of continuous subarrays that satisfy the condition.

Step-by-Step Algorithm

1. Initialize Deques and Pointers:

   • Start by creating two empty deques, maxQ and minQ. These will help us keep track of the maximum and minimum values within the current subarray.
   • Initialize two pointers: left to 0 (start of the subarray) and right to 0 (end of the subarray).
   • Also, initialize ans to 0, which will store the total count of continuous subarrays, and n to the length of the input array nums.

2. Iterate Over the Array:

   • Begin a loop with the right pointer moving from the start to the end of the array.
   • For each element at position right, perform the following steps:

3. Maintain Decreasing Order in maxQ:

   • While maxQ is not empty and the last element in maxQ is less than the current element (nums[right]), remove elements from the back of maxQ.
   • This step ensures that maxQ always contains elements in decreasing order from front to back, with the maximum value at the front.

4. Maintain Increasing Order in minQ:

   • Similarly, while minQ is not empty and the last element in minQ is greater than the current element (nums[right]), remove elements from the back of minQ.
   • This step ensures that minQ always contains elements in increasing order from front to back, with the minimum value at the front.

5. Add Current Element to Deques:

   • Add the current element (nums[right]) to both maxQ and minQ.

6. Adjust the left Pointer:

   • While the difference between the maximum value (maxQ.peekFirst()) and the minimum value (minQ.peekFirst()) is greater than 2:
     • If the element at the left pointer is equal to the first element in maxQ, remove it from maxQ.
     • If the element at the left pointer is equal to the first element in minQ, remove it from minQ.
     • Move the left pointer to the right by incrementing left.
     • This step ensures that the subarray always satisfies the condition max - min <= 2.

7. Count Valid Subarrays:

   • Add the number of valid subarrays ending at the right pointer to ans. The number of such subarrays is right - left + 1.

8. Continue Until End of Array:

   • Continue this process until the right pointer has iterated through the entire array.

9. Return the Result:

   • Finally, return ans, which contains the total number of valid continuous subarrays.

Algorithm Walkthrough

Let's consider the Input: nums = [1, 2, 2, 13, 1]

1. Initialization:

   • left = 0, right = 0, ans = 0.
   • maxQ = [], minQ = [].

2. Iteration 1 (right = 0):

   • Current element: nums[0] = 1.
   • maxQ and minQ are empty. So, add 1 to both maxQ and minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 1 - 1 = 0 (which is ≤ 2), the subarray [1] is valid.
   • Valid subarrays count: 1 (for the subarray [1]).
   • Update ans = ans + right - left + 1 = 0 + 0 + 0 + 1 = 1.
   • maxQ = [1], minQ = [1].

3. Iteration 2 (right = 1):

   • Current element: nums[1] = 2.
   • Maintain maxQ: Remove 1 from maxQ (since 1 < 2), then add 2 to maxQ.
   • Maintain minQ: Add 2 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 2 - 1 = 1 (which is ≤ 2), the subarrays [2] and [1, 2] are valid.
   • Valid subarrays count: right - left + 1 = 1 - 0 + 1 = 2 (for the subarrays [2] and [1, 2]).
   • Update ans = 3.
   • maxQ = [2], minQ = [1, 2].

4. Iteration 3 (right = 2):

   • Current element: nums[2] = 2.
   • Maintain maxQ: Add 2 to maxQ.
   • Maintain minQ: Add 2 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 2 - 1 = 1 (which is ≤ 2), the subarrays [2], [2, 2], and [1, 2, 2] are valid.
   • Valid subarrays count: right - left + 1 = 2 - 0 + 1 = 3 (for the subarrays [2], [2, 2], and [1, 2, 2]).
   • Update ans = 6.
   • maxQ = [2, 2], minQ = [1, 2, 2].

5. Iteration 4 (right = 3):

   • Current element: nums[3] = 13.
   • Maintain maxQ: Remove 2 and 2 from maxQ (since 2 < 13), then add 13 to maxQ.
   • Maintain minQ: Add 13 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 13 - 1 = 12 (which is > 2), we adjust the left pointer:
     • Move left to 1, remove 1 from minQ.
     • Since 13 - 2 = 11 (which is still > 2), move left to 2, remove 2 from minQ.
     • Since 13 - 2 = 11 (which is still > 2), move left to 3, remove 2 from minQ.
   • Now, with left = 3, maxQ.peekFirst() - minQ.peekFirst() = 13 - 13 = 0 (which is ≤ 2), the subarray [13] is valid.
   • Valid subarrays count: right - left + 1 = 3 - 3 + 1 = 1 (for the subarray [13]).
   • Update ans = 7.
   • maxQ = [13], minQ = [13].

6. Iteration 5 (right = 4):

   • Current element: nums[4] = 1.
   • Maintain maxQ: Add 1 to maxQ.
   • Maintain minQ: Remove 13 from minQ, add 1 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 13 - 1 = 12 (which is > 2), adjust the left pointer:
     • Move left to 4, remove 13 from maxQ.
   • Now, with left = 4, maxQ.peekFirst() - minQ.peekFirst() = 1 - 1 = 0 (which is ≤ 2), the subarray [1] is valid.
   • Valid subarrays count: right - left + 1 = 4 - 4 + 1 = 1 (for the subarray [1]).
   • Update ans = 8.
   • maxQ = [1], minQ = [1].

7. End of Loop:

   • The loop ends with right reaching the end of the array.
   • The final answer is 8, representing the total number of valid continuous subarrays.

Code