LeetCode 413 - Arithmetic Slices

The problem asks us to count how many contiguous subarrays of length at least three form an arithmetic sequence. An arithmetic sequence is one where the difference between every pair of adjacent elements is identical.

leetcodemediumarraydynamic-programmingsliding-window

LeetCode Problem 413

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Sliding Window

Solution

Problem Understanding

The problem asks us to count how many contiguous subarrays of length at least three form an arithmetic sequence.

An arithmetic sequence is one where the difference between every pair of adjacent elements is identical. For example:

  • [1, 3, 5, 7] has a constant difference of 2
  • [7, 7, 7, 7] has a constant difference of 0
  • [5, 1, -3] has a constant difference of -4

We are given an integer array nums, and we must count every contiguous subarray that satisfies this property.

The important detail is that we are counting subarrays, not subsequences. A subarray must consist of consecutive elements from the original array.

For example, in nums = [1,2,3,4], the valid arithmetic slices are:

  • [1,2,3]
  • [2,3,4]
  • [1,2,3,4]

So the answer is 3.

The constraints tell us several important things:

  • nums.length can be up to 5000
  • A brute-force cubic solution may become too slow
  • The numbers themselves are small, but the length is large enough that algorithmic efficiency matters

The most important edge cases include:

  • Arrays with fewer than three elements, since they can never form arithmetic slices
  • Arrays where all values are identical, because every sufficiently long subarray becomes arithmetic
  • Arrays where the arithmetic pattern repeatedly breaks and restarts
  • Negative differences, since arithmetic sequences are not limited to increasing numbers

Approaches

Brute Force Approach

The brute-force idea is to examine every possible subarray of length at least three and check whether it is arithmetic.

We can generate all subarrays using two nested loops:

  • Choose a starting index
  • Choose an ending index

For each subarray, we compute the common difference using the first two elements, then verify that every adjacent pair has the same difference.

This approach is correct because it explicitly checks every possible candidate subarray.

However, it is inefficient. There are O(n^2) subarrays, and checking each one may take O(n) time. That leads to a total complexity of O(n^3) in the worst case.

With n = 5000, this becomes far too slow.

Optimal Dynamic Programming Approach

The key observation is that arithmetic slices can be extended incrementally.

Suppose we already know that a subarray ending at index i - 1 forms arithmetic slices. If:

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

then any arithmetic slice ending at i - 1 can be extended by nums[i].

Additionally, the new triple:

nums[i-2], nums[i-1], nums[i]

also forms a new arithmetic slice.

This means we can maintain:

  • current, the number of arithmetic slices ending at the current index
  • total, the overall count

If the arithmetic condition holds:

current += 1
total += current

Otherwise:

current = 0

This allows us to process the array in one pass.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every subarray individually
Optimal O(n) O(1) Uses incremental arithmetic slice counting

Algorithm Walkthrough

  1. First, handle the trivial case where the array length is less than 3.

Since arithmetic slices require at least three elements, we immediately return 0. 2. Initialize two variables:

  • current, the number of arithmetic slices ending at the current position
  • total, the total number of arithmetic slices found so far

Initially, both are 0. 3. Iterate through the array starting from index 2.

We begin at index 2 because we need at least three elements to form an arithmetic slice. 4. For each index i, compare consecutive differences:

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

If they are equal, then the sequence continues the arithmetic pattern. 5. When the differences match:

  • Increment current by 1
  • Add current to total

This works because every previous arithmetic slice ending at i-1 can now extend to i, and the new length-3 slice also counts. 6. If the differences do not match:

  • Reset current to 0

This means the arithmetic chain has broken. 7. After processing all indices, return total.

Why it works

The algorithm maintains the invariant that current always represents the number of arithmetic slices ending at the current index.

If the arithmetic property continues at index i, then every valid slice ending at i-1 extends to a new valid slice ending at i. Additionally, the newest length-3 slice becomes valid. Therefore, the number of new slices increases by exactly one more than before.

If the arithmetic property breaks, no arithmetic slice can continue through the current index, so current resets to zero.

Because every arithmetic slice is counted exactly once when its ending index is processed, the final total is correct.

Python Solution

from typing import List

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)

        if n < 3:
            return 0

        current = 0
        total = 0

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

        return total

The implementation begins by checking whether the array contains at least three elements. If not, the function immediately returns 0.

The variable current tracks how many arithmetic slices end at the current index. The variable total accumulates the final answer.

The loop starts at index 2 because arithmetic slices require three consecutive elements. At each step, the code compares adjacent differences.

When the differences match, the arithmetic sequence continues. The code increments current, since every previous arithmetic slice can extend by one element. Then it adds current to total.

When the differences differ, the arithmetic chain breaks, so current resets to zero.

Finally, the function returns the accumulated total.

Go Solution

func numberOfArithmeticSlices(nums []int) int {
	n := len(nums)

	if n < 3 {
		return 0
	}

	current := 0
	total := 0

	for i := 2; i < n; i++ {
		if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
			current++
			total += current
		} else {
			current = 0
		}
	}

	return total
}

The Go implementation follows the same logic as the Python version.

Go slices already track their length, so we use len(nums) to determine whether the array is large enough.

Integer overflow is not a concern here because the constraints are small enough that the total count fits comfortably inside Go's int type.

The solution uses only constant extra space and performs a single pass through the array.

Worked Examples

Example 1

nums = [1,2,3,4]

We process the array starting from index 2.

i nums[i-2:i+1] Difference Check current total
2 [1,2,3] 1 == 1 1 1
3 [2,3,4] 1 == 1 2 3

Explanation:

At i = 2, we find one arithmetic slice:

[1,2,3]

At i = 3, the arithmetic pattern continues.

This creates:

[2,3,4]
[1,2,3,4]

So we add 2 more slices.

Final answer:

3

Example 2

nums = [1]

The array length is less than 3, so no arithmetic slice can exist.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is traversed once
Space O(1) Only a few variables are used

The algorithm performs a single linear scan through the array. Each iteration does constant work, consisting of a few arithmetic operations and comparisons.

No additional arrays or dynamic data structures are required, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)

        if n < 3:
            return 0

        current = 0
        total = 0

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

        return total

solution = Solution()

assert solution.numberOfArithmeticSlices([1, 2, 3, 4]) == 3  # basic increasing arithmetic sequence
assert solution.numberOfArithmeticSlices([1]) == 0  # single element
assert solution.numberOfArithmeticSlices([1, 2]) == 0  # only two elements
assert solution.numberOfArithmeticSlices([1, 1, 1]) == 1  # constant sequence
assert solution.numberOfArithmeticSlices([1, 3, 5, 7, 9]) == 6  # long arithmetic sequence
assert solution.numberOfArithmeticSlices([7, 7, 7, 7]) == 3  # repeated equal values
assert solution.numberOfArithmeticSlices([3, -1, -5, -9]) == 3  # negative difference
assert solution.numberOfArithmeticSlices([1, 2, 4, 6, 8]) == 3  # arithmetic sequence starts later
assert solution.numberOfArithmeticSlices([1, 2, 3, 8, 9, 10]) == 2  # separate arithmetic regions
assert solution.numberOfArithmeticSlices([1, 2, 3, 4, 5]) == 6  # multiple overlapping slices
assert solution.numberOfArithmeticSlices([1, 3, 8]) == 0  # no arithmetic slice
assert solution.numberOfArithmeticSlices([0, 0, 0, 0, 0]) == 6  # all zeros

Test Case Summary

Test Why
[1,2,3,4] Standard example with overlapping slices
[1] Minimum array size
[1,2] Still too short for a valid slice
[1,1,1] Difference of zero
[1,3,5,7,9] Long arithmetic progression
[7,7,7,7] Constant repeated values
[3,-1,-5,-9] Negative common difference
[1,2,4,6,8] Arithmetic pattern begins later
[1,2,3,8,9,10] Multiple disconnected arithmetic regions
[1,2,3,4,5] Many overlapping arithmetic slices
[1,3,8] No valid arithmetic slice
[0,0,0,0,0] All identical values

Edge Cases

One important edge case is arrays with fewer than three elements. Since the definition of an arithmetic slice requires at least three numbers, these inputs must immediately return 0. A naive implementation might accidentally treat pairs as valid sequences. The solution avoids this by checking the length at the beginning.

Another important edge case is arrays where every element is identical, such as [7,7,7,7]. Here, the common difference is 0, which is still a valid arithmetic progression. Some implementations incorrectly assume the difference must be nonzero. This solution simply compares adjacent differences, so zero differences work naturally.

A third important edge case occurs when the arithmetic pattern breaks and later resumes, such as [1,2,3,8,9,10]. The implementation correctly resets current to zero whenever the difference changes. This prevents invalid slices from being carried across disconnected arithmetic regions.

A fourth subtle edge case involves overlapping arithmetic slices. For example, [1,2,3,4,5] contains many valid subarrays that share elements. A naive implementation may undercount these overlapping sequences. The dynamic programming approach handles this correctly because current tracks how many arithmetic slices end at each position, automatically accounting for all overlaps.