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


  • 0
    H

    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
            
    

Log in to reply
 

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