Arithmetic Slices: Counting Arithmetic Subarrays

You are given an integer array nums. Return the number of contiguous subarrays (of length 3 or more) that form an arithmetic sequence, meaning the difference between consecutive elements is the same throughout.

This is LeetCode 413: Arithmetic Slices, and it is a beautiful example of how a small DP insight can turn a potentially quadratic problem into a clean linear scan. The trick is recognizing that each new element either extends the current arithmetic run or breaks it.

Why this problem matters

Arithmetic Slices sits at the intersection of two important patterns: contiguous subarray counting and linear DP. Many candidates try to enumerate all subarrays explicitly, but that approach is O(n^2) and misses the real lesson. The problem is designed to reward you for spotting how new arithmetic slices relate to the ones you already found.

The key idea is that when you extend an arithmetic run by one element, you do not just add one new slice. You add several, and the number of new slices is exactly one more than what the previous element contributed. This cascading relationship is the DP recurrence, and once you see it, the solution is just a few lines.

This pattern of "how many new things does this element create" shows up across many subarray-counting problems. Mastering it here gives you a reusable building block for harder variants.

The approach

Here is the core insight. Define dp[i] as the number of arithmetic slices that end at index i. At each index i (starting from 2), check whether the last three elements form an arithmetic triple:

nums[i] - nums[i-1] == nums[i-1] - nums[i-2]

If they do, then every arithmetic slice that ended at i-1 can be extended by one element to create a new slice ending at i. Plus there is one brand new slice of length 3 ending at i. So:

dp[i] = dp[i-1] + 1

If the triple is not arithmetic, the run breaks and dp[i] = 0.

The total answer is the sum of all dp[i] values. Since dp[i] only depends on dp[i-1], you can replace the array with a single variable.

def numberOfArithmeticSlices(nums):
    n = len(nums)
    if n < 3:
        return 0

    dp = 0
    total = 0

    for i in range(2, n):
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
            dp += 1
            total += dp
        else:
            dp = 0

    return total

Step-by-step walkthrough

Let's trace through the example nums = [1, 2, 3, 4]. At each step we track dp (the number of arithmetic slices ending here) and total (the running sum of all slices found so far).

Why does dp[3] = 2? When we reach index 3, the triple [2, 3, 4] is arithmetic, so that is one new slice. But the previous dp[2] = 1 told us there was already one slice ending at index 2, namely [1, 2, 3]. Extending that slice gives us [1, 2, 3, 4], which is a second new slice. So dp[3] = dp[2] + 1 = 2, and those two new slices bring the total to 3.

This is the cascading property in action. Each element in a continuing arithmetic run contributes more new slices than the one before it. If a run has length k, the number of arithmetic slices in it is 1 + 2 + ... + (k - 2) = (k-2)(k-1)/2. The DP approach computes this incrementally without needing to track the run length explicitly.

Here is the explicit DP array version for clarity:

def numberOfArithmeticSlices(nums):
    n = len(nums)
    if n < 3:
        return 0

    dp = [0] * n

    for i in range(2, n):
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
            dp[i] = dp[i - 1] + 1

    return sum(dp)

The optimized version above replaces dp with a single integer, exactly the same space-reduction trick you see in Climbing Stairs. When the recurrence only looks back one step, one variable is all you need.

Complexity analysis

Time: O(n). One pass through the array, doing O(1) work at each index.

Space: O(1). Two variables (dp and total), regardless of input size.

Edge cases to watch for

• Fewer than 3 elements like [1, 2]: no triple is possible, return 0.
• No arithmetic slices like [1, 3, 8, 2]: differences keep changing, dp stays 0 the entire time.
• All elements the same like [5, 5, 5, 5, 5]: common difference is 0, which is valid. A run of length 5 gives (5-2)(5-1)/2 = 6 slices.
• Negative differences like [10, 7, 4, 1]: difference is -3 throughout. Works the same way.
• Multiple separate runs like [1, 2, 3, 8, 10, 12]: two arithmetic runs of length 3. Each contributes 1 slice, total = 2. The dp variable resets to 0 at index 3, then starts climbing again at index 5.

The building blocks

This problem is built on two reusable patterns:

1. Linear DP with one-step lookback. The recurrence dp[i] = dp[i-1] + 1 (or 0) only depends on the previous value. You can compress the entire DP array into a single variable, giving O(1) space. This is the same skeleton used in Maximum Subarray (Kadane's algorithm) and Climbing Stairs. Different recurrences, same brick.

2. Counting new contributions incrementally. Instead of enumerating all valid subarrays, you ask "how many new valid subarrays does this element create?" and accumulate a running total. This avoids the O(n^2) brute force and is a technique you will see again in problems like Longest Increasing Subsequence, where tracking what each element adds to the count is more efficient than recounting everything.

Once you recognize these two building blocks, the solution falls into place: "one-step DP to count slices ending here, running total to collect them all."

From understanding to recall

You have just read through the DP approach and the cascading dp[i] = dp[i-1] + 1 recurrence makes sense. But recognizing the pattern during an interview, under pressure, is a different skill entirely. If you solved this problem once three weeks ago, could you reproduce the recurrence and the space optimization from memory?

Spaced repetition bridges that gap. By revisiting the "does this element extend the arithmetic run?" pattern at increasing intervals, the DP setup and the single-variable optimization become automatic. After a few reps, you will not need to rederive the recurrence. You will just see it.

Related posts

• Maximum Subarray - Another linear DP with one-step lookback, the extend-or-restart decision behind Kadane's algorithm
• Climbing Stairs - The simplest linear DP problem, same space-optimization trick of replacing the array with a single variable
• Maximum Product Subarray - Contiguous subarray DP with a twist, tracking both min and max to handle sign flips