# Python from O(n^2) to O(n)

• The intuitive solution is to do this in O(n^2), add one to the count of total arithmetic slices, if A[i:j] is an arithmetic slice, then we can add one, and check if A[i:j+1] is also an arithmetic slice.

Otherwise, check starting from A[i+1:] since we need to have a consecutive sequence to continue.

``````def numberOfArithmeticSlices(self, A):
if len(A) < 3:
return 0
count = 0

for i in range(len(dp)-2):
for j in range(i, len(A)):
if (A[j]-A[j-1]) == (A[j-1] -A[j-2]):
count += 1
else:
break
return count
``````

We can optimize this to O(N) by noting the fact that we only need to keep track of the previous ending, and the length of our current sequence.

For example:
Given [1,2,3,4,5]
[1,2,3] = 1
When we expand to 4, because [1,2,3,4] is a continuation of our last sequence of [1,2,3] we need to account for this, as well as if the arithmetic sequence were to start at 2 and be [2,3,4].

Our previous incrementer kept track of how long the last sequence was, so we just need to add one to it.

``````class Solution(object):
def numberOfArithmeticSlices(self, A):
if len(A) < 3:
return 0

last_diff = A[1] - A[0]
len_sequence = 0
count = 0

for i in range(2, len(A)):
if A[i] - A[i-1] == last_diff:
len_sequence +=1
count += len_sequence
else:
len_sequence = 0
last_diff = A[i]-A[i-1]
return count

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.