_1218. Longest Arithmetic Subsequence of Given Difference.md

1218. Longest Arithmetic Subsequence of Given Difference

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : May 31, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Hash Table, Dynamic Programming

Acceptance Rate : 54.56 %

---

Solutions

• m1218.py

Python

m1218.py

# Solution is O(n) both space and time
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        # for O(1) lookups
        referenceDict = {}

        for i in arr :
            if i - difference in referenceDict.keys() :
                referenceDict[i] = 1 + referenceDict[i - difference]
            else :
                referenceDict[i] = 1
            
        return max(referenceDict.values())
        



        # Old attempt that was TLE
        # visited = {}

        # @cache
        # def findLongest(currentIndex: int) -> int:
        #     pointer = currentIndex - 1
        #     while pointer >= 0 :
        #         if arr[currentIndex] - arr[pointer] == difference :
        #             return findLongest(pointer) + 1
        #         pointer -= 1
        #     return 1
        
        # maxx = 0
        # for i in range(len(arr) - 1, -1, -1):
        #     if i in visited.keys():
        #         continue
        #     maxx = max(findLongest(i), maxx)

        # return maxx