Problem Description

You need to find how many arithmetic subarrays exist in a given integer array.

An arithmetic array must have:

• At least 3 elements
• The same difference between any two consecutive elements

For example:

• [1,3,5,7,9] is arithmetic (difference = 2)
• [7,7,7,7] is arithmetic (difference = 0)
• [3,-1,-5,-9] is arithmetic (difference = -4)

A subarray is a contiguous portion of the original array. You need to count all possible subarrays that form arithmetic sequences.

Given an array nums, return the total count of arithmetic subarrays.

Example breakdown: If nums = [1,2,3,4], the arithmetic subarrays are:

• [1,2,3] (difference = 1)
• [2,3,4] (difference = 1)
• [1,2,3,4] (difference = 1)

So the answer would be 3.

The key insight is that when you have a longer arithmetic sequence, it contains multiple smaller arithmetic subsequences. For instance, an arithmetic sequence of length n contains (n-1)(n-2)/2 arithmetic subarrays of length 3 or more.

Intuition

The key observation is that when we extend an arithmetic sequence by one more element, we create additional arithmetic subarrays.

Consider an arithmetic sequence like [1,2,3,4,5]. When we're at element 5, we know it extends the existing arithmetic pattern. This creates new subarrays:

• [3,4,5] (length 3)
• [2,3,4,5] (length 4)
• [1,2,3,4,5] (length 5)

Notice that if we already have an arithmetic sequence of length k, adding one more element that maintains the same difference creates k-1 new arithmetic subarrays (all ending at the new element).

This leads us to a counting strategy: as we scan through the array, we track how many consecutive elements maintain the same difference. Each time we extend the sequence, we add the count of new subarrays formed.

For example, with [1,2,3,4]:

• At position 2 (value 3): We have our first arithmetic subarray [1,2,3], count = 1
• At position 3 (value 4): We extend the sequence, creating [2,3,4] and [1,2,3,4], adding 2 more

The pattern emerges: if cnt represents how many times we've extended the current arithmetic sequence, then adding one more element creates cnt new arithmetic subarrays. This is because each extension adds subarrays of all possible lengths ending at the current position.

When the difference changes, we reset our count since we're starting a new potential arithmetic sequence. The elegance of this approach is that we only need to track the current difference and how many extensions we've made, giving us an O(n) solution with O(1) space.

Solution Approach

The implementation uses a sliding window-like approach with two key variables:

• d: tracks the current difference between consecutive elements (initialized to 3000, an impossible difference given the problem constraints)
• cnt: counts how many times we've extended the current arithmetic sequence (initialized to 0)

Algorithm walkthrough:

1. Iterate through adjacent pairs: Using pairwise(nums), we examine each pair of consecutive elements (a, b).

2. Check if the sequence continues: For each pair, calculate the difference b - a:

   • If b - a == d, the arithmetic sequence continues:
     • Increment cnt by 1
     • Add cnt to the answer (this represents all new arithmetic subarrays ending at position b)
   • If b - a != d, we've encountered a new difference:
     • Update d = b - a to track the new difference
     • Reset cnt = 0 since we're starting a new potential sequence

3. Accumulate the count: The key insight is that when cnt = k, it means we've found k new arithmetic subarrays ending at the current position:

   • When cnt = 1: one subarray of length 3
   • When cnt = 2: two subarrays (lengths 3 and 4)
   • When cnt = k: k subarrays (lengths 3 through k+2)

Example trace with nums = [1,2,3,4]:

• Pair (1,2): difference = 1, new difference, set d=1, cnt=0, ans=0
• Pair (2,3): difference = 1 = d, increment cnt=1, add to ans=0+1=1
• Pair (3,4): difference = 1 = d, increment cnt=2, add to ans=1+2=3

The algorithm correctly counts 3 arithmetic subarrays: [1,2,3], [2,3,4], and [1,2,3,4].

Time Complexity: O(n) - single pass through the array Space Complexity: O(1) - only using constant extra variables

Example Walkthrough

Let's trace through the algorithm with nums = [1, 3, 5, 6, 7, 8]:

Initial state: d = 3000 (impossible difference), cnt = 0, ans = 0

Step 1: Pair (1, 3)

• Difference: 3 - 1 = 2
• Since 2 ≠ 3000, this is a new difference
• Update: d = 2, cnt = 0, ans = 0

Step 2: Pair (3, 5)

• Difference: 5 - 3 = 2
• Since 2 == d, the arithmetic sequence continues
• Update: cnt = 1, ans = 0 + 1 = 1
• This counts the subarray [1, 3, 5]

Step 3: Pair (5, 6)

• Difference: 6 - 5 = 1
• Since 1 ≠ 2, we have a new difference
• Update: d = 1, cnt = 0, ans = 1

Step 4: Pair (6, 7)

• Difference: 7 - 6 = 1
• Since 1 == d, the arithmetic sequence continues
• Update: cnt = 1, ans = 1 + 1 = 2
• This counts the subarray [5, 6, 7]

Step 5: Pair (7, 8)

• Difference: 8 - 7 = 1
• Since 1 == d, the arithmetic sequence continues
• Update: cnt = 2, ans = 2 + 2 = 4
• This counts two new subarrays: [6, 7, 8] and [5, 6, 7, 8]

Final answer: 4 arithmetic subarrays

• [1, 3, 5] (difference = 2)
• [5, 6, 7] (difference = 1)
• [6, 7, 8] (difference = 1)
• [5, 6, 7, 8] (difference = 1)

The algorithm efficiently counts all arithmetic subarrays by tracking when consecutive differences remain the same, accumulating the count as sequences extend.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm iterates through the array once using pairwise(nums), which generates consecutive pairs of elements. For an array of length n, this produces n-1 pairs. Each iteration performs constant time operations:

• Computing the difference b - a: O(1)
• Comparison b - a == d: O(1)
• Updating variables cnt, d, and ans: O(1)

Therefore, the overall time complexity is O(n-1) = O(n).

Space Complexity: O(1) - constant extra space.

The algorithm uses only a fixed number of variables:

• ans: stores the total count of arithmetic slices
• cnt: stores the current count of consecutive differences
• d: stores the current common difference
• a, b: temporary variables for the current pair

The pairwise() function returns an iterator that doesn't create a new data structure but generates pairs on-the-fly, so it doesn't consume additional space proportional to the input size.

Common Pitfalls

Pitfall 1: Incorrect Counter Reset Logic

The Problem: A common mistake is resetting the counter to 1 instead of 0 when encountering a new difference. This happens when developers think "we already have one pair with the new difference, so let's start counting from 1."

Incorrect Implementation:

for prev_num, curr_num in pairwise(nums):
    difference = curr_num - prev_num
  
    if difference == current_difference:
        consecutive_pairs += 1
    else:
        current_difference = difference
        consecutive_pairs = 1  # ❌ Wrong! Should be 0
  
    total_slices += consecutive_pairs

Why it's wrong: When we encounter a new difference, we've only seen ONE pair with that difference. To form an arithmetic subarray, we need at least TWO pairs with the same difference (creating 3 elements total). Setting consecutive_pairs = 1 would incorrectly count 2-element sequences as arithmetic subarrays.

Correct Solution: Always reset to 0 when starting a new potential sequence. The counter represents how many ADDITIONAL pairs we've found with the same difference after the first pair.

Pitfall 2: Off-by-One Error in Manual Iteration

The Problem: When not using pairwise(), developers often make indexing errors:

Incorrect Implementation:

for i in range(len(nums)):  # ❌ Goes out of bounds
    difference = nums[i+1] - nums[i]
    # ... rest of logic

Correct Solution:

for i in range(len(nums) - 1):  # ✓ Stops at second-to-last element
    difference = nums[i+1] - nums[i]
    # ... rest of logic

Pitfall 3: Misunderstanding the Count Accumulation

The Problem: Some developers mistakenly think they should add 1 to the answer whenever they find a valid arithmetic sequence continuation, rather than adding the current count value.

Incorrect Implementation:

if difference == current_difference:
    consecutive_pairs += 1
    total_slices += 1  # ❌ Wrong! Should add consecutive_pairs

Why it's wrong: When consecutive_pairs = k, it means we can form k different arithmetic subarrays ending at the current position:

• If consecutive_pairs = 2, we have subarrays of length 3 and 4 ending here
• We should add 2 to our total, not 1

Visual Example: For array [1,2,3,4,5]:

• At position 3: we can form [1,2,3] (count = 1)
• At position 4: we can form [2,3,4] AND [1,2,3,4] (count = 2)
• At position 5: we can form [3,4,5], [2,3,4,5], AND [1,2,3,4,5] (count = 3)

The accumulation pattern follows the triangular number sequence, which is why we add the current count value each time.