Solution: Arithmetic Slices

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #413 (Medium): 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:

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%).

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%).

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%).

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%).

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;
    }
};