# Arithmetic Slices
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/arithmetic-slices)
Canonical: https://scaleengineer.com/dsa/problems/arithmetic-slices
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Baidu](https://scaleengineer.com/companies/baidu)
---
## Problem
An integer array is called arithmetic if it consists of **at least three elements** and if the difference between any two consecutive elements is the same.

* For example, `[1,3,5,7,9]`, `[7,7,7,7]`, and `[3,-1,-5,-9]` are arithmetic sequences.

Given an integer array `nums`, return _the number of arithmetic **subarrays** of_ `nums`.

A **subarray** is a contiguous subsequence of the array.

**Example 1:**

**Input:** nums = [1,2,3,4]
**Output:** 3
**Explanation:** We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

**Example 2:**

**Input:** nums = [1]
**Output:** 0

**Constraints:**

* `1 <= nums.length <= 5000`
* `-1000 <= nums[i] <= 1000`

# Approaches
## Refined Brute Force
This approach iterates through all possible starting elements of an arithmetic subarray. For each starting element, it extends the subarray to the right, one element at a time, and checks if the arithmetic property is maintained. If it is, a valid arithmetic slice has been found, and the count is incremented.
**Time:** O(n^2), where n is the length of the input array. The two nested loops give a quadratic time complexity in the worst case. · **Space:** O(1), as we only use a few variables to store the count and difference, not dependent on the input size.
**Pros:** Simple to understand and implement.; Improves upon the naive O(n^3) brute-force approach.; Uses constant extra space.
**Cons:** Inefficient for large inputs due to the quadratic time complexity.; Performs many redundant checks. For example, when checking `[1,2,3,4]`, the check for `[2,3,4]` being arithmetic is repeated.
### Explanation
We can fix the starting index `i` of a potential arithmetic subarray and then iterate through the subsequent elements to find all valid arithmetic subarrays that begin at `i`.

The algorithm works as follows:
1.  Initialize a counter `count` to 0.
2.  Iterate with an outer loop from `i = 0` to `nums.length - 2`. This `i` will be the starting index of our potential slices.
3.  For each `i`, calculate the required common difference `diff = nums[i + 1] - nums[i]`.
4.  Start an inner loop with `j` from `i + 2` to `nums.length - 1`.
5.  In the inner loop, check if `nums[j] - nums[j - 1]` is equal to `diff`.
6.  If they are equal, it means the subarray `nums[i...j]` is an arithmetic slice. So, we increment our `count`.
7.  If they are not equal, it means any longer subarray starting at `i` cannot be arithmetic. We can break the inner loop and move to the next starting index `i`.
8.  After all loops complete, `count` will hold the total number of arithmetic subarrays.

```java
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int diff = nums[i + 1] - nums[i];
            for (int j = i + 2; j < nums.length; j++) {
                if (nums[j] - nums[j - 1] == diff) {
                    count++;
                } else {
                    break;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate with an outer loop for `i` from `0` to `nums.length - 3`.
- For each `i`, calculate the common difference `diff = nums[i + 1] - nums[i]`.
- Start an inner loop with `j` from `i + 2` to `nums.length - 1`.
- If `nums[j] - nums[j - 1] == diff`, it means the subarray `nums[i...j]` is an arithmetic slice, so increment `count`.
- If the differences are not equal, any longer subarray starting at `i` cannot be arithmetic, so break the inner loop.
- After the loops complete, return `count`.

## Dynamic Programming
This approach uses dynamic programming to solve the problem in linear time. We define a DP state `dp[i]` as the number of arithmetic subarrays that *end* at index `i`. By building up the solution from smaller subproblems, we can efficiently calculate the total count.
**Time:** O(n), where n is the length of the array. We iterate through the array once to fill the DP table. · **Space:** O(n), as we use a DP array of size `n` to store the intermediate results.
**Pros:** Efficient with linear time complexity.; The DP state and transition are logical and easy to follow.
**Cons:** Uses extra space proportional to the input size, which can be optimized.
### Explanation
An arithmetic subarray must have at least three elements. So, for an arithmetic subarray to end at index `i`, the subarray `nums[i-2], nums[i-1], nums[i]` must be arithmetic. This means `nums[i] - nums[i-1] == nums[i-1] - nums[i-2]`.

Let `dp[i]` be the number of arithmetic subarrays ending at index `i`.
- If `nums[i] - nums[i-1] == nums[i-1] - nums[i-2]`, then any arithmetic subarray ending at `i-1` can be extended by `nums[i]` to form a new arithmetic subarray ending at `i`. Additionally, `nums[i-2], nums[i-1], nums[i]` forms a new arithmetic subarray of length 3. This gives us the recurrence relation: `dp[i] = dp[i-1] + 1`.
- If the condition `nums[i] - nums[i-1] == nums[i-1] - nums[i-2]` is false, then no arithmetic subarray can end at `i`, so `dp[i] = 0`.

The base cases are `dp[0] = 0` and `dp[1] = 0` as a slice needs at least 3 elements.
The final answer is the sum of all values in the `dp` array, as `dp[i]` only counts slices ending at `i`, and we need the total count over all possible ending positions.

```java
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        int[] dp = new int[nums.length];
        int totalCount = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
            }
            // If the condition is false, dp[i] remains 0 by default initialization.
            totalCount += dp[i];
        }
        return totalCount;
    }
}
```
### Algorithm
- If the array length `n` is less than 3, return 0.
- Create a DP array `dp` of size `n`, initialized to zeros.
- Initialize `totalCount = 0`.
- Loop for `i` from `2` to `n-1`.
- If `nums[i] - nums[i-1] == nums[i-1] - nums[i-2]`:
  - Set `dp[i] = dp[i-1] + 1`.
- Add the value of `dp[i]` to `totalCount` in each iteration.
- Return `totalCount`.

## Constant Space Dynamic Programming
This is the most optimal approach. It refines the dynamic programming solution by observing that the calculation for the number of slices ending at index `i` only depends on the number of slices ending at the immediately preceding index, `i-1`. This allows us to eliminate the DP array and use only a single variable, reducing space complexity to constant while maintaining linear time complexity.
**Time:** O(n), where n is the length of the array. A single pass through the array is performed. · **Space:** O(1), as we only use a couple of variables to keep track of the counts, regardless of the input size.
**Pros:** Optimal solution with linear time and constant space complexity.; Highly efficient for all valid input sizes.
**Cons:** The logic might be slightly less intuitive at first glance compared to the version with the explicit DP array.
### Explanation
Instead of maintaining a full `dp` array, we only need to keep track of the number of arithmetic slices ending at the previous index `i-1`. Let's call this variable `currentSlices`.

We iterate through the array starting from index 2. In each iteration `i`, we check if `nums[i]`, `nums[i-1]`, and `nums[i-2]` form an arithmetic progression.
- If `nums[i] - nums[i-1] == nums[i-1] - nums[i-2]`:
  - It means we can extend all the arithmetic slices ending at `i-1` by one more element, plus we form one new slice of length 3. The number of slices ending at `i` will be one more than the number of slices ending at `i-1`.
  - So, we increment `currentSlices`.
- If the condition is false:
  - The arithmetic sequence is broken. No arithmetic slice can end at `i`.
  - We must reset `currentSlices` to 0.

In each step of the loop, the value of `currentSlices` represents the number of new arithmetic slices that end at the current index `i`. We add this value to a `totalSlices` counter.

```java
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        int totalSlices = 0;
        int currentSlices = 0; // Represents dp[i-1] in the DP approach
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                currentSlices += 1;
            } else {
                currentSlices = 0;
            }
            totalSlices += currentSlices;
        }
        return totalSlices;
    }
}
```
### Algorithm
- If the array length `n` is less than 3, return 0.
- Initialize `totalSlices = 0` and `currentSlices = 0`.
- Loop for `i` from `2` to `n-1`.
- If `nums[i] - nums[i-1] == nums[i-1] - nums[i-2]`:
  - Increment `currentSlices` by 1.
- Else:
  - Reset `currentSlices` to 0.
- Add `currentSlices` to `totalSlices` in each iteration.
- Return `totalSlices`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfArithmeticSlices(int[] nums) {
    int ans = 0, cnt = 0;
    int d = 3000;
    for (int i = 0; i < nums.length - 1; ++i) {
      if (nums[i + 1] - nums[i] == d) {
        ++cnt;
      } else {
        d = nums[i + 1] - nums[i];
        cnt = 0;
      }
      ans += cnt;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfArithmeticSlices(vector<int> &nums) {
    int ans = 0, cnt = 0;
    int d = 3000;
    for (int i = 0; i < nums.size() - 1; ++i) {
      if (nums[i + 1] - nums[i] == d) {
        ++cnt;
      } else {
        d = nums[i + 1] - nums[i];
        cnt = 0;
      }
      ans += cnt;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int: ans = cnt = 0 d = 3000 for a, b in pairwise(nums): if b - a == d: cnt += 1 else: d = b - a cnt = 0 ans += cnt return ans

```