https://leetcode.com/problems/arithmetic-slices

Let us understand, what arithmetic slice means on the example 1, 2, 3, 4, 5, 10, 12, 14, 16.

First of all, we can take only adjacent elements, we can not take elements [1, 3, 5] for example.

Let us evaluate differences between adjacent elements.

1, 1, 1, 1, 5, 2, 2, 2

We can say that arithmetic slice in original list are groups of >=2 elements with equal values. So, what we can do is to iterate over groups of elements and calcualate answer for each group. Let us look at first one: we can take:

1, 2, 3, 2, 3, 4, 3, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In general case, if we have group of lenth k in list of differences, we have exaclty k(k-1)/2 arithmetic slices. Note, that this also deal correctly with k = 1 case, where we have arithmetic progression of length 2, which is not slice.

However if you use groupby and will write (len(list(j))-1)*len(list(j))//2 for ..., it is not going to work properly, because groupby is iterator objext and it will take next j, which is not correct. We can use here the following trick: note, that

k(k-1)/2 = ((2*k-1)^2 - 1)/ 8, which uses only one yield from iterator groupby.

Complexity: time complexity is just O(n), because we iterate list once to get differences and iterate it second time, evaluating sum. Space complexity is O(n), because we create list B here. If you know how to still keep it oneliner but make it O(1) space, please, let me know!

class Solution:
    def numberOfArithmeticSlices(self, A):
        B =  [j-i for i,j in zip(A, A[1:])]
        return sum(((2*len(list(j))-1)**2-1)//8 for i, j in groupby(B))

Oneliner

It can be written as:

return sum(((2*len(list(j))-1)**2-1)//8 for i, j in groupby([j-i for i,j in zip(A, A[1:])]))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0413