# Python solutions with detailed explanations

• Solution

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

Brute Force: Time and Space: O(N^2)

• Note that a slice must be atleast of size 3. Single element and 2 elements do not make up a slice.
• If dp[i,j] = dp[i, j-1] and (A[j]-A[j-1]) == (A[j-1]-A[j-2]). This leads to a N^2 space and time solution.
• We mark continous elements (i,I+1) as True. Then for every start point (i), we start scanning sequences from i+2 i.e. atleast size 3.
• This gives a TLE
``````class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
dp = [[False]*N for _ in range(N)]
cnt = 0
for i in range(N):
if i+1 < N:
dp[i][i+1] = True
for i in range(N):
for j in range(i+2,N):
dp[i][j] = dp[i][j-1] and ((A[j]-A[j-1]) == (A[j-1] - A[j-2]))
if dp[i][j]:
cnt += 1
return cnt
``````

Space Optimized to O(N^2) with Time O(N^2)

• We can easily optimize the space and realize we just need a single variable. N^2 time and O(1) space.
• The problem is defined as the "number of sequences which start at index i". Now a sequence starting at i can be length 3, 4, 5,..., but every squence must have the same consecutive difference defined by A[i+1]-A[i].
• The moment we hit a number that cannot be in the sequence, we break.
``````class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
N, cnt = len(A), 0
for i in range(N-1):
diff = (A[i+1]-A[i])
for j in range(i+2,N):
if (A[j]-A[j-1]) == diff:
cnt = cnt + 1
else:
break
return cnt
``````

Optimized O(N) time and O(1) space solution

• With a bit of an insight, it is possible to have an O(N) solution.
• Let us define two variables: cur is the number of sequences starting from index i. ans is the total number of sequences for array A[0:i+1].
• Consider the number of sequence that start from index 2 or element 3. The array will be [1,2,3]. We can see that (1,2,3) is a sequence (3-2)==(2-1) and curr = 1 and ans =1.
• Now when we add another number 4, the new array is [1,2,3,4]. Since 4-3 is same as 2-1,
we conclude curr=2 i.e. sequences starting from index 2. Now how many new sequences have been created with the addition of 4? Ans: (1,2,3,4) and (2,3,4) or 2 or curr. Hence ans = ans + curr.
• Now test this by adding another number 5. The new array is [1,2,3,4,5]. The number of sequences starting from 3 are now 3 and hence curr = 3. This addition (5), has created three more sequences: (1,2,3,4,5); (2,3,4,5); (2,3,4). Hence ans = ans + curr
``````class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
if N < 3: return 0
ans, cnt, delta = 0, 0, A[1] - A[0]
for x in range(2, N):
if A[x] - A[x - 1] == delta:
cnt += 1
ans += cnt
else:
delta, cnt = A[x] - A[x - 1], 0
return ans
``````

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