23.07.14 Today’s Leetcode

1218. Longest Arithmetic Subsequence of Given Difference (medium)

TLE Solution with O(n^2)

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        n = len(arr)
        temp = []
        res = 1
        for i in range(n):
            count = 1
            k = i
            j = i + 1
            while j < n:
                diff = arr[j] - arr[k]
                if diff == difference:
                    k = j
                    count += 1
                j += 1
            res = max(res, count)

        return res 

Successive Solution with O(n)

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        n = len(arr)
        temp = defaultdict(int)
        for i in range(n - 1, -1, -1):
            cur = arr[i]
            temp[cur] = max(1, temp[cur + difference] + 1)

        return max(temp.values())