Problem Description

You are given a 0-indexed integer array nums. Your task is to find the total number of continuous subarrays.

A subarray is called continuous if it satisfies the following condition:

• For any two elements in the subarray at indices i₁ and i₂, the absolute difference between their values must be at most 2. In other words, |nums[i₁] - nums[i₂]| ≤ 2 for all pairs of indices within the subarray.

This means that in a continuous subarray, the difference between any two elements (not just adjacent ones) cannot exceed 2. Essentially, all elements in the subarray must be within a range of size 2.

For example:

• [1, 2, 3] is continuous because all pairwise differences are at most 2
• [1, 2, 4] is NOT continuous because |4 - 1| = 3 > 2
• [5, 5, 5] is continuous because all elements are the same

The problem asks you to count all possible continuous subarrays in the given array. Remember that a subarray must be contiguous (elements appear consecutively in the original array) and non-empty.

The solution uses a sliding window approach with two pointers (i and j) where j represents the right end of the current window. A SortedList maintains all elements in the current window in sorted order. When adding a new element, if the difference between the maximum and minimum elements exceeds 2, the window shrinks from the left by removing elements and moving pointer i forward. For each valid window position, the number of continuous subarrays ending at position j is equal to the window size, which gets added to the answer.

Intuition

The key insight is that we need to efficiently count all subarrays where the maximum difference between any two elements is at most 2. A brute force approach would check every possible subarray, but that would be inefficient.

Let's think about this problem differently. For any valid continuous subarray, if we know its maximum and minimum elements, we can quickly check if it's valid by verifying that max - min ≤ 2. This observation suggests we should track the maximum and minimum values as we build subarrays.

Now, consider building subarrays by extending them to the right one element at a time. As we add each new element, we need to:

1. Check if the current window (from some left position to the current position) is still valid
2. Count how many valid subarrays end at the current position

The critical realization is that if we have a valid window from index i to index j, then all subarrays ending at j and starting at any index from i to j are also valid. This means the number of valid subarrays ending at position j equals the current window size.

Why use a sliding window? When we add a new element and the window becomes invalid (max - min > 2), we need to shrink it from the left. The window property ensures that once we find the leftmost valid position, all positions to its right form valid subarrays with the current ending position.

The SortedList data structure is perfect here because:

• It maintains elements in sorted order automatically
• We can quickly access the minimum (sl[0]) and maximum (sl[-1]) elements
• We can efficiently add and remove elements while maintaining order

This approach cleverly converts a seemingly complex counting problem into a sliding window problem where we maintain a valid range and accumulate counts based on window sizes.

Learn more about Queue, Sliding Window, Monotonic Queue and Heap (Priority Queue) patterns.

Solution Approach

The solution uses a sliding window technique with two pointers combined with a SortedList data structure to efficiently count continuous subarrays.

Implementation Details:

1. Initialize Variables:

   • ans = 0: Accumulates the total count of continuous subarrays
   • i = 0: Left pointer of the sliding window
   • sl = SortedList(): Maintains elements in the current window in sorted order

2. Iterate Through the Array: For each element x in nums (where the implicit right pointer j is the current index):

   a. Add current element to window:

   sl.add(x)

   The SortedList automatically maintains sorted order after insertion.

   b. Shrink window if invalid:

   while sl[-1] - sl[0] > 2:
       sl.remove(nums[i])
       i += 1

   • Check if the difference between max (sl[-1]) and min (sl[0]) exceeds 2
   • If yes, remove the leftmost element nums[i] from the SortedList
   • Move the left pointer i forward
   • Continue until the window becomes valid again

   c. Count valid subarrays ending at current position:

   ans += len(sl)

   The window size len(sl) equals the number of valid subarrays ending at the current position. This is because any subarray starting from index i to the current index forms a valid continuous subarray.

3. Return the Result: After processing all elements, return ans which contains the total count.

Why This Works:

• The sliding window maintains the invariant that all elements within it form a valid continuous subarray (max - min ≤ 2)
• When we're at position j with a valid window starting at i, we know that subarrays [i, j], [i+1, j], ..., [j, j] are all valid
• The number of such subarrays is exactly j - i + 1, which equals len(sl)
• By accumulating these counts for each position, we get the total number of continuous subarrays

Time Complexity: O(n log n) where n is the length of the array, due to SortedList operations Space Complexity: O(n) in the worst case when all elements form a valid continuous subarray

Example Walkthrough

Let's walk through the solution with nums = [5, 4, 2, 4].

Initial State:

• ans = 0, i = 0, sl = SortedList([])

Step 1: Process index j=0, element=5

• Add 5 to sl: sl = [5]
• Check validity: max - min = 5 - 5 = 0 ≤ 2 ✓ (valid)
• Count subarrays ending at index 0: len(sl) = 1
  • This counts subarray [5]
• Update: ans = 0 + 1 = 1

Step 2: Process index j=1, element=4

• Add 4 to sl: sl = [4, 5] (sorted)
• Check validity: max - min = 5 - 4 = 1 ≤ 2 ✓ (valid)
• Count subarrays ending at index 1: len(sl) = 2
  • This counts subarrays [5,4] and [4]
• Update: ans = 1 + 2 = 3

Step 3: Process index j=2, element=2

• Add 2 to sl: sl = [2, 4, 5] (sorted)
• Check validity: max - min = 5 - 2 = 3 > 2 ✗ (invalid)
• Shrink window:
  • Remove nums[0] = 5: sl = [2, 4], i = 1
  • Check validity: max - min = 4 - 2 = 2 ≤ 2 ✓ (now valid)
• Count subarrays ending at index 2: len(sl) = 2
  • This counts subarrays [4,2] and [2]
• Update: ans = 3 + 2 = 5

Step 4: Process index j=3, element=4

• Add 4 to sl: sl = [2, 4, 4] (sorted)
• Check validity: max - min = 4 - 2 = 2 ≤ 2 ✓ (valid)
• Count subarrays ending at index 3: len(sl) = 3
  • This counts subarrays [4,2,4], [2,4], and [4]
• Update: ans = 5 + 3 = 8

Final Result: ans = 8

The 8 continuous subarrays are:

1. [5] - single element
2. [5,4] - max-min = 1
3. [4] - single element
4. [4,2] - max-min = 2
5. [2] - single element
6. [4,2,4] - max-min = 2
7. [2,4] - max-min = 2
8. [4] - single element

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n) and the space complexity is O(n), where n is the length of the array nums.

Time Complexity Analysis:

• The outer loop iterates through each element in nums once, contributing O(n).
• For each element, we perform sl.add(x) which takes O(log k) time where k is the current size of the SortedList.
• The while loop condition sl[-1] - sl[0] > 2 accesses min and max in O(log k) time.
• Inside the while loop, sl.remove(nums[i]) takes O(log k) time.
• In the worst case, each element is added once and removed once throughout the entire execution.
• Since each element goes through add/remove operations with O(log n) complexity (as the SortedList can contain at most n elements), the total time complexity is O(n × log n).

Space Complexity Analysis:

• The SortedList sl stores elements from the current window.
• In the worst case (when all elements satisfy the condition max - min ≤ 2), the SortedList could contain all n elements.
• Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Regular List Instead of SortedList

A common mistake is attempting to use a regular Python list and manually finding min/max values:

Incorrect Approach:

window = []  # Regular list
for current_num in nums:
    window.append(current_num)
    while max(window) - min(window) > 2:  # O(n) operation!
        window.remove(nums[left])
        left += 1

Problem: Finding min/max in an unsorted list takes O(n) time for each check, degrading overall complexity to O(n²).

Solution: Use SortedList which maintains sorted order and provides O(1) access to min/max elements via window[0] and window[-1].

2. Incorrect Window Size Calculation

Some might incorrectly calculate the number of valid subarrays:

Incorrect:

total_subarrays += right - left + 1  # Using explicit indices

Problem: If you're using an enumerated loop or managing indices manually, it's easy to mix up the calculation, especially if the right pointer isn't explicitly tracked.

Solution: Use len(window) which directly gives the current window size, avoiding index arithmetic errors.

3. Not Handling Element Removal Properly

A subtle bug can occur when removing elements from the window:

Incorrect:

while window[-1] - window[0] > 2:
    window.remove(window[0])  # Wrong! Removing from sorted position
    left += 1

Problem: The window is sorted, but we need to remove the element at the original array position nums[left], not the minimum element in the sorted window.

Solution: Always remove nums[left] from the window, not window[0]:

window.remove(nums[left])

4. Missing Edge Cases

Forgetting to handle single-element subarrays or empty arrays:

Solution: The current implementation handles these correctly:

• Single elements automatically satisfy the condition (difference with itself is 0)
• Empty arrays return 0 (the loop doesn't execute)

5. Integer Overflow in Other Languages

While not an issue in Python, in languages like Java or C++, the accumulation of subarray counts could overflow:

Solution for other languages:

long totalSubarrays = 0;  // Use long instead of int

6. Forgetting to Import SortedList

The code won't run without the proper import:

Solution: Always include:

from sortedcontainers import SortedList

Note: In competitive programming platforms, you might need to implement your own balanced BST if SortedList isn't available.