< Back 1218. Longest Arithmetic Subsequence of Given Difference We're asked to find the longest subsequence of numbers that all have a difference of difference from left to right. We solve this using dynamic programming, but not with a memoization table like usual. Instead, we maintain dictionary of numbers seen, because, for a subsequence, we're going to have to look backwards an arbitrary number of spaces. The dictionary contains, for a given number, num, the length of the subsequence prior to reaching that number wherein all numbers have a difference of difference. So for example, if we're looking at 2 and the difference is 2, we the compliment would be 4. If we've seen 4 before, it will return from a dictionary lookup, and then we append 1 to the subsequence and store dp[2]. Otherwise, the subsequence for dp[2] will be 1. Across this process, we maximize the answer for the highest length subsequence we've seen so far. The solution is as follows: from collections import defaultdict class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: dp = defaultdict(int) ans = 1 for num in arr: dp[num] = dp[num - difference] + 1 ans = max(ans, dp[num]) return ans _ Time Complexity: O(n) - Where n is the length of arr, we iterate through the number list once. _ Space Complexity: O(n) - We maintain a memoization dictionary of size n.