Python solution with detailed explanation


  • 0
    G

    Solution

    Arithmetic Slices II - Subsequence https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

    Dynamic Programming Solution

    • sub_problem[i,d] = Number of arthimetic sequences of length 2 or more which end at index i and have difference as d. Note we said length 2 or more and not 3.
    • Say we have an array called cache where every element of cache is a dictionary. The key for dictionary is difference d and value is number of sequences which end at i with difference d.
    • sub_problem[i,d] = sub_problem[j,d] + 1 iff A[i]-A[j] == d. The 1 in this equation represents the new subsequence of size 2 comprising of A[j], A[i]. Imagine array [2,2,3,4]. Say we are at index 2. Now we want to find the distribution of all sequences which end at index 2. Now for index 1 and 0, we notice a size 2 sequence of (2,3) and (2,3). These two would be added in the count of all subsequences ending at i.
    • We maintain a count of all size 2 subsequences and call it subs_len_2. Once we are done processing an index, we add all subsequences which end at index i to result. Finally we remove the count of size 2 subsequences from result and return the result.
    from collections import defaultdict
    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            cache = [defaultdict(int) for _ in range(len(A))]
            result, subs_len_2 = 0, 0
            for i in range(1, len(A)):
                for j in range (i-1,-1,-1):
                    curr_diff = A[i]-A[j]
                    cache[i][curr_diff], subs_len_2 = cache[i][curr_diff]+1, subs_len_2+1
                    if curr_diff in cache[j]:
                        cache[i][curr_diff] += cache[j][curr_diff]
                result += sum(cache[i].values())
            return result - subs_len_2
    

    Succinct Code

    • The above code can be made a bit more clever so that we do not need to maintain a count of size 2 subsequences.
    class Solution1(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            cache = [{} for _ in range(len(A))]
            result = 0
            for i in range(1, len(A)):
                for j in range (i-1,-1,-1):
                    curr_diff = A[i]-A[j]
                    cache[i].setdefault(curr_diff, 0)
                    cache[i][curr_diff] += 1
                    if curr_diff in cache[j]:
                        cache[i][curr_diff] += cache[j][curr_diff]
                        result += cache[j][curr_diff]
            return result
    

Log in to reply
 

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