Solution: Arithmetic Slices
Tags: algorithms, javascript, java, python
Published: 2021-02-18 09:51:41

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/arithmetic-slices/discuss/1071127/).*

---

####[Leetcode Problem #413 (*Medium*): Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/)

---

***Description:***

*A sequence of numbers 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, these are arithmetic sequences:*
 - `1, 3, 5, 7, 9`
 - `7, 7, 7, 7`
 - `3, -1, -5, -9`

*The following sequence is not arithmetic.*
 - `1, 1, 2, 5, 7`

*A zero-indexed array `A` consisting of `N` numbers is given. A slice of that array is any pair of integers `(P, Q)` such that `0 <= P < Q < N`.*

*A slice `(P, Q)` of the array `A` is called arithmetic if the sequence:
`A[P], A[P + 1], ..., A[Q - 1]`, `A[Q]` is arithmetic. In particular, this means that `P + 1 < Q`.*

*The function should return the number of arithmetic slices in the array `A`.*

---

***Examples:***

Example:||
|---:|---|
*Input:*|A = [1, 2, 3, 4]
*Output:*|3
*Explanation:*|3 arithmetic slices in A: [1, 2, 3],<br>[2, 3, 4] and [1, 2, 3, 4] itself.

---

***Idea:***

It's obviously very easy to find the difference between consecutive elements of an array, so it should also be a simple matter to iterate through the input array (**A**) and use a variable (**diff**) to keep track of what the most recently seen difference is and another variable (**count**) to keep track of how many consecutive elements make up the current streak.

Some basic math will tell us that the number of possible combinations for a given **count** is a triangular number: with **4** numbers, for example, it's possible to make up **10** (**1+2+3+4**) different number combinations ranging in length from **1** to **4**.

The problem states that our minimum slice is **3** numbers, but since **3** numbers is actually **2** differences, and we're dealing with differences, we'll use **2** instead of **3** here. The number of **2+** length combinations is just a **0-indexed triangular number** instead of a **1-indexed triangular number**. So as in our earlier example, **4** consecutive differences yields **6** (**0+1+2+3**) possible combinations.

But rather than obtaining a **count** and then using the 0-indexed triangular number equation (**n * (n - 1) / 2**), we can just build this triangular number iteratively, since we're iterating anyway.

Normally, when building a triangular number iteratively, you would *first* increment the **count** and *then* add that **count** to the **ans**. In this case, we can either start the **count** at **-1**, or wait until *after* adding **count** to **ans** to increment **count**.

Doing this, we can find our answer easily in O(n) time with minimal processing overhead.

---

***Implementation:***

Technically, this problem doesn't list a constraint for the values in **A**. Since we're storing the difference between two elements in a variable, that could cause problems if the numbers range too broadly.

To get around that, we'd have to perform even more array calls on each iteration to avoid storing the differences in variables.

Also, Java and C++ have typed variables, so we can just use the max int value for the starting value of **diff**.

Otherwise, we'd have to set the initial **diff** to **A[1] - A[0]**, the initial **count** to **1**, start our iteration at **i = 2**, and lead with an **if** statement to prevent situations where those array calls go out-of-bounds.

Given all of that, I opted for the somewhat safe assumption that there's some kind of reasonable constraint, but I figured it would be wise to at least point that out here.

---

***Javascript Code:***

The best result for the code below is **68ms / 38.3MB** (beats 96% / 74%).
```javascript
var numberOfArithmeticSlices = function(A) {
    let count = 0, diff, ans = 0
    for (let i = 1; i < A.length; i++) {
        let newDiff = A[i] - A[i-1]
        if (newDiff === diff) ans += count++
        else diff = newDiff, count = 1
    }
    return ans
};
```

---

***Python Code:***

The best result for the code below is **24ms / 14.1MB** (beats 100% / 100%).
```python
class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        count, ans, diff = 0, 0, None
        for i in range(1, len(A)):
            newDiff = A[i] - A[i-1]
            if newDiff == diff:
                ans += count
                count += 1
            else:
                diff = newDiff
                count = 1
        return ans
```

---

***Java Code:***

The best result for the code below is **0ms / 36.5MB** (beats 100% / 96%).
```java
class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int count = 0, ans = 0, diff = Integer.MAX_VALUE;
        for (int i = 1; i < A.length; i++) {
            int newDiff = A[i] - A[i-1];
            if (newDiff == diff) ans += count++;
            else {
                diff = newDiff;
                count = 1;
            }
        }
        return ans;
    }
}
```

---

***C++ Code:***

The best result for the code below is **0ms / 7.2MB** (beats 100% / 87%).
```c++
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int count = 0, ans = 0, diff = INT_MAX;
        for (int i = 1; i < A.size(); i++) {
            int newDiff = A[i] - A[i-1];
            if (newDiff == diff) ans += count++;
            else {
                diff = newDiff;
                count = 1;
            }
        }
        return ans;
    }
};
```