BinarySearch 0887 Longest Arithmetic Subsequence with Difference Constraint

Problem statement

https://binarysearch.com/problems/Longest-Arithmetic-Subsequence-with-Difference-Constraint/

Solution

Equal to Leetcode 1218. Longest Arithmetic Subsequence of Given Difference

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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())