Arithmetic Slices

Medium
316.

Arithmetic Slices

Arithmetic Slices is a medium coding problem on arrays and dynamic programming, asked in Amazon, Meta and Bloomberg interviews.

An integer array is arithmetic if it has at least three elements and the difference between consecutive elements is constant.

Given an integer array nums, return the number of arithmetic subarrays (contiguous slices).

Example 1

Input
nums = [1,2,3,4]
Output
3
Explanation
The slices are [1,2,3], [2,3,4] and [1,2,3,4].

Example 2

Input
nums = [1]
Output
0

Example 3

Input
nums = [1,3,5,7,9]
Output
6

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Arithmetic Slices — Solution in Python, Java & C++

Arithmetic Slices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Arithmetic Slices is a medium coding problem on arrays and dynamic programming, asked in Amazon, Meta and Bloomberg interviews.

Problem statement

An integer array is arithmetic if it has at least three elements and the difference between consecutive elements is constant.

Given an integer array nums, return the number of arithmetic subarrays (contiguous slices).

Example 1

Input: nums = [1,2,3,4]
Output: 3
Explanation: The slices are [1,2,3], [2,3,4] and [1,2,3,4].

Example 2

Input: nums = [1]
Output: 0

Example 3

Input: nums = [1,3,5,7,9]
Output: 6

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Hints for Arithmetic Slices

  1. Hint 1

    Let cur be the number of arithmetic slices ending at the current index.

  2. Hint 2

    If the current difference matches the previous one, cur grows by one; otherwise it resets to zero.

  3. Hint 3

    The answer is the running sum of cur — each step adds the slices that end right there.

How to solve Arithmetic Slices

Let cur be the number of arithmetic slices ending at the current index; it grows by one while the difference matches and resets otherwise. Sum cur over the array.

Approach

  1. For i from 2: if nums[i] - nums[i-1] == nums[i-1] - nums[i-2], cur += 1 and total += cur; else cur = 0.
  2. Return total.

Why it works

If the arithmetic run ending at i has length L ≥ 3, exactly L - 2 slices end at i, which is what cur counts after each extension.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Slices of length 2 do not count.

Reference solution

Python

def numberOfArithmeticSlices(nums) -> int:
    total = cur = 0
    for i in range(2, len(nums)):
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
            cur += 1
            total += cur
        else:
            cur = 0
    return total

Java

public static int numberOfArithmeticSlices(int[] nums) {
    int total = 0, cur = 0;
    for (int i = 2; i < nums.length; i++) {
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            cur++;
            total += cur;
        } else {
            cur = 0;
        }
    }
    return total;
}

C++

int numberOfArithmeticSlices(vector<int>& nums) {
    int total = 0, cur = 0;
    for (int i = 2; i < (int) nums.size(); i++) {
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            cur++;
            total += cur;
        } else {
            cur = 0;
        }
    }
    return total;
}

JavaScript

var numberOfArithmeticSlices = function(nums) {
    let total = 0, cur = 0;
    for (let i = 2; i < nums.length; i++) {
        if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
            cur++;
            total += cur;
        } else {
            cur = 0;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming