Domain 2MediumCORE

Arithmetic Slices

We need to count the number of contiguous subarrays within nums that form an arithmetic sequence. An arithmetic sequence requires at least three elements and a constant difference between adjacent pairs.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Dynamic Programming

413. Arithmetic Slices

Model: qwen3.5:9b
Topics: Math,Dynamic Programming
FAANG asked: 1
Acceptance rate: 60.0%


Problem Breakdown

We need to count the number of contiguous subarrays within nums that form an arithmetic sequence. An arithmetic sequence requires at least three elements and a constant difference between adjacent pairs.

Inputs: A list of integers nums.
Outputs: The total integer count of valid arithmetic slices found in the array.

Constraints & Edge Cases to Consider:

  • Length < 3: If the input has fewer than 3 elements, no slice can exist (return 0).
  • Negative Numbers/Differences: Arithmetic sequences can have negative differences or zero difference (e.g., [7,7,7]). The logic must handle diff == 0 correctly.
  • Overflow: Python handles large integers automatically, so standard integer overflow isn’t a concern here given the constraints (−1000≤nums[i]-1000 \le nums[i]).

Intuition

A brute-force approach would iterate through every possible subarray (start and end indices) and check if it’s arithmetic. This results in O(N3)O(N^3) or at best O(N2)O(N^2) time complexity, which is inefficient for N=5000.

The key insight here relies on Dynamic Programming logic without necessarily needing a full DP table. Notice that an arithmetic slice ending at index i can only be formed if the difference between nums[i] - nums[i-1] matches the previous difference (nums[i-1] - nums[i-2]).

If this condition holds, we are extending existing valid sequences. Specifically:

  • If a sequence of length kk (elements) ending at index i−1i-1 is arithmetic, adding one more element that maintains the same difference creates exactly (current_run+1)(current\_run + 1) new slices ending at ii.
  • Essentially, if we have found x valid arithmetic subarrays ending at position i-1, and the current step continues the pattern, then there are now x+1 valid subarrays ending at i. If the pattern breaks (difference changes), any sequence of length ≥3\ge 3 cannot continue, so our running counter resets to 0.

Approach

We will iterate through the array starting from index 2 (since we need a minimum of 3 elements). We maintain two variables:

  1. total_slices: Accumulates the final answer.
  2. current_run: Tracks how many arithmetic slices end at the current position.

For each element, calculate the difference between it and its predecessor (diff). Compare this to the previous difference stored in a variable (let’s call it prev_diff or just check against the last valid step).

  • If nums[i] - nums[i-1] == prev_diff: Increment current_run. Add current_run to total_slices.
  • Else: Reset current_run to 0.

We need a way to track if we are currently in an arithmetic run, so I’ll initialize the loop logic carefully or handle index 2 separately. A cleaner implementation initializes prev_diff inside the loop or handles indices i=1i=1 and i≥2i \ge 2. Given Python’s flexibility, iterating from index 2 is straightforward provided we track differences correctly.

Complexity Analysis

  • Time: O(N)O(N) - We traverse the array exactly once with a single pass.
  • Space: O(1)O(1) - We only use two integer variables (total_slices, current_run) regardless of input size (excluding recursion stack or DP table).

Solution

def numberOfArithmeticSlices(nums):
    # If fewer than 3 elements, no arithmetic slice is possible.
    if len(nums) < 3:
        return 0
    
    total_slices = 0
    current_run = 0
    
    # We need at least indices i-2 and i to calculate a difference sequence.
    # Start loop from index 2 (the third element).
    for i in range(2, len(nums)):
        diff_curr = nums[i] - nums[i-1]
        
        if diff_curr == (nums[i-1] - nums[i-2]):
            current_run += 1
            total_slices += current_run
        else:
            # Pattern broken; reset the running counter for this position.
            current_run = 0
            
    return total_slices

Edge Cases Handled

  • Length < 3: The initial check if len(nums) < 3 returns 0 immediately, preventing index errors or incorrect counts on small arrays like [1].
  • Constant Sequence (e.g., [7,7,7]): Difference is always 0. Logic holds because 0==00 == 0, incrementing the run correctly to count all sub-slices of identical elements.
  • Negative Differences: Subtraction handles negative numbers naturally in Python; e.g., [-1,-3,-5] yields diff -2, which matches consistently across steps.