Leetcode 1218. Longest Arithmetic Subsequence of Given Difference

Problem statement

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

Solution

Iterate from left to right and for each value keep the longest progression ending with this value.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def longestSubsequence(self, arr, diff):
        last = Counter()
        for i, x in enumerate(arr):
            last[x] = max(last[x], 1, last[x - diff] + 1)
        return max(last.values())