Python solutions with detailed explanations


  • 0
    G

    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
    

Log in to reply
 

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