### View *Longest Arithmetic Subsequence of Given Difference* on LeetCode

## Statistics

**Time Spent Coding**

20 minutes

**Time Complexity**

O(n) - Each element in the array must be visisted, resulting in the O(n) time complexity.

**Space Complexity**

O(n) - Each element in the array must be stored in the dictionary, resulting in the O(n) space complexity.

**Runtime Beats**

91.64% of other submissions

## Explanation

For each element in the array, check if its ancestor (`n - diff`

) is in the dictionary, if not then add it with a value of 1, if it is then increment its ancestors value by 1. Doing this repeatedly for each value in the array allows us to dynamically update subsequences, becuase if multiple element are within the same subsequence they will incrementally increase as each new element in the subsequence is discovered.

## Data Structure Used

**Hash Table (Set) -** An unordered container of non-repeating values.

**Visual Examples**

An array being transformed into a set, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11

class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
dic = {}
for n in arr:
if n - difference not in dic:
dic[n] = 1
else:
dic[n] = dic[n - difference] + 1
return max(dic.values())