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 - A 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