Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.
 
Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

 
Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

Difficulty: interview

Starter code:

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        

Solutions:
from collections import defaultdict

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        count_dict = defaultdict(int)
        for num in arr:
            count_dict[num] = count_dict[num-difference] + 1
        return max(count_dict.values())


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        hs = dict()
        for num in arr:
            if num - difference in hs:
                hs[num] = hs[num - difference] + 1
            if num not in hs and num - difference not in hs:
                hs[num] = 1
        # print(hs)
        return max(item for item in hs.values())

from collections import defaultdict
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if not arr:
            return 0
        dp = [1 for _ in range(len(arr))]
        seen = defaultdict(list)
        for i, num in enumerate(arr):
            prev = num - difference
            choices = seen[prev]
            for j in choices:
                dp[i] = max(dp[j] + 1, dp[i])
            seen[num].append(i)        
        return max(dp)

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = [1 for a in arr]
        ele = collections.defaultdict(list)
        for i,x in enumerate(arr):
            ele[x].append(i)
        for i, a in enumerate(arr):
            if a - difference in ele:
                for j in ele[a-difference]:
                    if j<i:
                        dp[i] = max(dp[j] + 1,dp[i])
        return max(dp)

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        seen = Counter()
        for v in arr:
            seen[v] = seen[v - difference] + 1
        return max(seen.values())


class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        mx = max(arr)
        mn = min(arr)
        d = dict()
        for i in range(-10**4,10**4+1):
            d[i] = 0
        n = len(arr)
        #print(d)
        if diff>0:
            d[arr[0]] = 1
            for i in range(1,n):
                if arr[i]-diff>=mn:
                    d[arr[i]] = max(d[arr[i]],d[arr[i]-diff]+1)
                else:
                    d[arr[i]] = 1
        else:
            arr = arr[::-1]
            #print(arr)
            d[arr[0]] = 1
            for i in range(1,n):
                if arr[i]+diff>=mn:
                    d[arr[i]] = max(d[arr[i]],d[arr[i]+diff]+1)
                else:
                    d[arr[i]] = 1
        #print(d)
        return max(list(d.values()))

class Solution:
    # brute force
#     def longestSubsequence(self, arr: List[int], difference: int) -> int:
#         ret = 0
#         for i in range(len(arr)):
#             n = 1
            
#             start = arr[i]
#             j = i + 1
#             while j < len(arr):
#                 if arr[j] - start == difference:
#                     n += 1
#                     start = arr[j]
#                 j += 1
                    
#             ret = max(ret, n)
                
                
                
#         return ret

    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        d = dict() # k=last, value=chain
        ret = 0
        for i,n in enumerate(arr):
            if n - difference not in d:
                d[n] = 1
            else:
                d[n] = d[n-difference] + 1
                
            ret = max(ret, d[n])
        return ret
            
            


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        current = {}
        for x in arr:
            old = x - difference
            if old in current:
                count = current[old]
                del current[old]
                current[x] = count + 1
            elif x not in current:
                current[x] = 1
            #print(f'{x, current}')
        return max(current.values())


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        sub_dict = {}
        n = len(arr)
        
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        max_len = 1

        for i in range(n - 1, -1, -1):
            value = arr[i]
            new_k_v = []
            
            dd = value + difference
            if dd in sub_dict:
                sub_dict[value] =  max(sub_dict.get(value, 0), sub_dict[dd] + 1)
                max_len = max(sub_dict[value], max_len)
                
            if value not in sub_dict:
                sub_dict[value] = 1
        
        return max_len


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

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        res = dict()
        max_seq = 0
        for a in arr:
            res[a] = res.get(a-difference, 0) + 1
        return max(res.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = [0] * 40001
        d = 20000
        opt = 0
        for e in arr:
            dp[e+d] = dp[e-difference + d] + 1
            opt = max(opt, dp[e+d])

        return opt         

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = [0  for _  in range(len(arr))]
        lookup = {}
        for i in range(len(arr)):
            if arr[i] not in lookup:
                lookup[arr[i]] = [i]
            else:
                lookup[arr[i]].append(i)
        for i in range(len(arr)-1, 0, -1):
            if arr[i] - difference in lookup:
                dp[i] = max(1, dp[i])
                for index in lookup[arr[i] -difference]:
                    if index < i:
                        dp[index] = dp[i] + 1
        return max(dp) if max(dp) > 0 else 1

class Solution:
    def longestSubsequence(self, arr: List[int], d: int) -> int:
        if not arr:
            return 0
        cache={}
        maxc=0
        for i in arr:
            if i-d in cache:
                cache[i]=cache[i-d]+1
            else:
                cache[i]=1
            maxc=max(maxc,cache[i])
        return maxc

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

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp, res = [0  for _  in range(len(arr))], 1
        lookup = {}
        for i in range(len(arr)):
            if arr[i] not in lookup:
                lookup[arr[i]] = [i]
            else:
                lookup[arr[i]].append(i)
        for i in range(len(arr)-1, 0, -1):
            diff = arr[i] - difference
            if  diff in lookup:
                dp[i] = max(1, dp[i])
                for index in lookup[diff]:
                    if index < i:
                        dp[index] = dp[i] + 1
                        res = max(res, dp[index])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        m = dict()
        for ind,num in enumerate(arr):
            if num in m:
                m[num].append(ind)
            else:
                m[num] = [ind]
        dp = []
        longest = 1
        for ind,num in enumerate(arr):
            if (num-difference) in m:
                possible_sol = []
                for diff_ind in m[num-difference]:
                    if diff_ind < len(dp):
                        possible_sol.append(dp[diff_ind] + 1)
                if possible_sol == []:
                    dp.append(1)
                else:
                    curr_max = max(possible_sol)
                    dp.append(curr_max)
                    if curr_max > longest:
                        longest = curr_max
                        
            else:
                dp.append(1)
        return longest

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dic = {}
        for i in range(len(arr)):
            temp = False
            if arr[i] - difference in list(dic.keys()):
                dic[arr[i]] = dic[arr[i] - difference] + [arr[i]]
                if arr[i] != arr[i] - difference:
                    dic.pop(arr[i] - difference)
                temp = True
            elif arr[i] in list(dic.keys()):
                temp = True
            
            # for k in list(dic.keys()):
            #     if k + difference == arr[i]:
            #         # print(k, difference, arr[i])
            #         dic[arr[i]] = dic[k] + [arr[i]]
            #         if arr[i] != k:
            #             dic.pop(k)
            #         temp = True
            #     elif k == arr[i]:
            #         temp = True
            if not temp:
                dic[arr[i]] = [arr[i]]
            # print(arr[i], dic)
        return max(list([len(x) for x in list(dic.values())]))


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = defaultdict(int) # Longest subseq that ends with they key. 
        for i,elem in enumerate(arr):
            dp[elem] = 1+dp[elem-difference]
        
        maxElem = 0
        for key in dp:
            maxElem = max(maxElem,dp[key])
            
        return maxElem

from collections import defaultdict
class Solution:
    # 先写出brute force solution O(n^2)，在下面
    # 再尝试用dp优化 
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        n = len(arr)
        ret = 0
        
        mappings = defaultdict(list)
        for i, v in enumerate(arr):
            mappings[v].append(i)
            
        M = [-1 for i in range(n)]
        
        def dp(i):
            if i == n-1:
                return 1
            
            if M[i] != -1:
                return M[i]
            
            M[i] = 1
            for j in mappings[arr[i]+difference]:
                if j > i:
                    M[i] += dp(j)
                    break
            
            return M[i]
        
        for i in range(n):
            ret = max(ret, dp(i))
            
        return ret
    
    
#     def longestSubsequence(self, arr: List[int], difference: int) -> int:
#         n = len(arr)
#         ret = 0
        
#         for i, num in enumerate(arr):
#             cur = num
#             length = 1
#             for j in range(i+1, n):
#                 if arr[j] == cur + difference:
#                     length += 1
#                     cur = arr[j]
#             ret = max(ret, length)
        
#         return ret


class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        mx = -float('inf')
        mn = float('inf')
        n = 0
        for i in arr:
            mx = max(mx,i)
            mn = min(mn,i)
            n+=1
        
        d = dict()
        for i in range(mn,mx+1):
            d[i] = 0
        #print(d)
        if diff>0:
            d[arr[0]] = 1
            for i in range(1,n):
                if arr[i]-diff>=mn:
                    d[arr[i]] = max(d[arr[i]],d[arr[i]-diff]+1)
                else:
                    d[arr[i]] = 1
        else:
            arr = arr[::-1]
            #print(arr)
            d[arr[0]] = 1
            for i in range(1,n):
                if arr[i]+diff>=mn:
                    d[arr[i]] = max(d[arr[i]],d[arr[i]+diff]+1)
                else:
                    d[arr[i]] = 1
        #print(d)
        return max(list(d.values()))

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


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        mp = {}
        res = 0
        for num in arr:
            currlen = 1
            if num-difference in mp:
                currlen = mp[num-difference]+1
            mp[num] = max(mp.get(num,1),currlen)
            res = max(res, currlen)
        
        return res


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        if len(arr) == 1:
            return 1
        memo = {}
        res = 0
        for i in range(len(arr)-1, -1, -1):
            if arr[i]+difference not in memo:
                memo[arr[i]] = 1
            else:
                memo[arr[i]] = memo[arr[i]+difference] + 1
            
            res = max(res, memo[arr[i]])
        return res
            
        


from collections import defaultdict
def lis(a, diff):
    lis = {}
    for i in range(len(a)):
        lis[a[i]]= lis.get(a[i]-diff,0) +1
    return max(lis.values())
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        return lis(arr, difference)

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        indexMap = defaultdict(list)
        
        dp = [0] * len(arr)
        maxSeq = 0
        
        for i, num in enumerate(arr):
            if num - diff in indexMap:
                for newIndex in indexMap[num - diff]:
                    dp[i] = max(dp[i], dp[newIndex])
            dp[i] += 1
            maxSeq = max(maxSeq, dp[i])
                
            
            indexMap[num].append(i)
            
        return maxSeq


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        max_val = 10000
        min_val = -10000
        diff = [0 for i in range(max_val - min_val + 1)]
        res = 1
        for x in arr:
            if x - difference >= min_val and x - difference <= max_val and diff[x-difference+max_val] >= diff[x+max_val]:
                diff[x+max_val] = diff[x-difference+max_val] + 1
            else:
                diff[x+max_val] = max(1, diff[x+max_val])
            res = max(res, diff[x+max_val])
        return res


from collections import defaultdict
import bisect
class Solution:
    # 先写出brute force solution O(n^2)，在下面
    # 再尝试用dp优化 
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        n = len(arr)
        ret = 0
        
        mappings = defaultdict(list)
        for i, v in enumerate(arr):
            mappings[v].append(i)
            
        M = [-1 for i in range(n)]
        
        def dp(i):
            if i == n-1:
                return 1
            
            if M[i] != -1:
                return M[i]
            
            M[i] = 1
            next_indexes = mappings[arr[i]+difference]
            j = bisect.bisect_right(next_indexes, i)
            
            if j < len(next_indexes):
                M[i] += dp(next_indexes[j])
            
            # for j in mappings[arr[i]+difference]:
            #     if j > i:
            #         M[i] += dp(j)
            #         break
        
            return M[i]
        
        for i in range(n):
            ret = max(ret, dp(i))

        return ret
    
    
#     def longestSubsequence(self, arr: List[int], difference: int) -> int:
#         n = len(arr)
#         ret = 0
        
#         for i, num in enumerate(arr):
#             cur = num
#             length = 1
#             for j in range(i+1, n):
#                 if arr[j] == cur + difference:
#                     length += 1
#                     cur = arr[j]
#             ret = max(ret, length)
        
#         return ret


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        maxs = 1
        for num in arr:
            dp[num]=dp.get(num-difference,0)+1
            if dp[num]>maxs:
                maxs=dp[num]
        return maxs

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        memo = Counter()
        for a in arr:
            memo[a] = memo[a - difference] + 1
        return max(memo.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        ans = 1
        table = {}
        for a in arr:
            prev = a - difference
            if prev in table:
                table[a] = table[prev] + 1
            else:
                table[a] = 1
            ans = max(ans, table[a])
        return ans


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if not arr:
            return 0
        dp = dict()
        for num in arr:
            prev = num - difference 
            if prev in dp:
                dp[num] = 1 + dp.get(prev, 0)
            else:
                dp[num] = 1
        return max(dp.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = [1]*len(arr)
        ans = 1
        seen = {}
        for i in range(len(arr)):
            if(arr[i]-difference in seen):
                dp[i]=1+dp[seen[arr[i]-difference]]
            seen[arr[i]]=i
        return max(dp)

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        mp = collections.defaultdict(int)
        ans = 0
        for a in arr:
            mp[a] = (1+mp[a-difference])
            ans = max(ans,mp[a])
        return ans


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        n = len(arr)
        dp = defaultdict(int)
        
        for i in arr:
            dp[i] = max(dp[i], dp[i-difference] + 1)
            
        return max(dp.values())
        


class Solution:
    def longestSubsequence(self, arr: List[int], d: int) -> int:
        cnt = defaultdict(int)
        for i in arr:
            cnt[i] = cnt[i-d] + 1
        return max(cnt.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp, res = {}, 0
        for i in arr:
            dp[i] = dp.get(i-difference, 0) + 1
            res = max(res, dp[i])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        res = 0
        for num in arr:
            dp[num] = 1 + dp.get(num-difference,0)
            res = max(res, dp[num])
            
        return res


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if len(arr) == 1:
            return 1
        dp = [1] * len(arr)
        dic = {arr[0]:0}
        for i in range(1, len(dp)):
            dic[arr[i]] = i
            if arr[i] - difference in dic:
                dp[i] = max(dp[i], dp[dic[arr[i]-difference]]+1)
        return max(dp)

class Solution:
    def longestSubsequence(self, arr: List[int], d: int) -> int:
        memo=dict()
        #arr.sort()
        for a in arr:
            if a-d in list(memo.keys()):
                memo[a]=memo[a-d]+1
            else:
                memo[a]=1
        return max(list(memo.values()))


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        l = len(arr)
        index_map = {}
        for i in range(l):
            
            if (arr[i] - difference) in index_map:
                j = index_map[arr[i]-difference]
                dp[i] = dp.get(j, 1) + 1
            index_map[arr[i]] = i
        return max(dp.values()) if dp else 1

from collections import defaultdict

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        elemToLen = defaultdict(int)
        best = 0
        for x in arr:
            elemToLen[x] = max(elemToLen[x], elemToLen[x - difference] + 1)
            best = max(best, elemToLen[x])
        return best

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        n = len(arr)
        ans = 0
        for i in range(n):
            if arr[i] - difference in dp:
                dp[arr[i]] = dp[arr[i] - difference] + 1
            else:
                dp[arr[i]] = 1
            ans = max(ans, dp[arr[i]])
            
        return ans

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        l = len(arr)
        index_map = {}
        res = 1
        for i in range(l):
            if (arr[i] - difference) in index_map:
                j = index_map[arr[i]-difference]
                dp[i] = dp.get(j, 1) + 1
                if dp[i] > res:
                    res = dp[i]
            index_map[arr[i]] = i
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if not arr:
            return 0
        
        max_len = 0
        dp = [0] * len(arr)
        prev_max_len = {}
        for i, num in enumerate(arr):
            if (key := arr[i] - difference) in prev_max_len:
                dp[i] = prev_max_len[key] + 1
            else:
                dp[i] = 1
            prev_max_len[arr[i]] = dp[i]
            max_len = max(max_len, dp[i])
        return max_len

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        mem=collections.defaultdict(int)
        #以各数结尾的子序列的长度
        res=0
        for n in arr:
            if mem[n-difference]+1>mem[n]:
                mem[n]=mem[n-difference]+1
            res=max(res,mem[n])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        res = {}
        for num in arr:
            res[num] = res.get(num - diff,0)+1
        return max(res.values())


# Brute force O(n^2) time and O(1) space
# O(n) time and O(1) space
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        cnt = collections.Counter()
        ans = 0
        for num in arr:
            cnt[num] = cnt[num-difference] + 1
            ans = max(ans, cnt[num])
        return ans


class Solution:
    '''
    
    arr = [1,2,3,4] d = 1
    
    0 - 1
    1 - 2 - 1 -> 1 += 1
    
    
    arr = [1,3,5,7] d = 1
    
    0: 1
    1: 3 - 1 -> 2 -> 1
    2: 5 - 
    
    
    
    '''
    import collections 
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        dp = {}
        
        max_len = 0
        
        for i in arr:
            dp[i] = dp.get(i - difference, 0) + 1
            
            max_len = max(max_len, dp[i])
            
        return max_len

import collections

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        prev_seq = collections.defaultdict(int)
        max_seq = 1
        for x in reversed(arr):
            target = x + difference
            x_seq = prev_seq[target] + 1
            max_seq = max(max_seq, x_seq)
            prev_seq[x] = max(prev_seq[x], x_seq)
        return max_seq
            
        


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        tail = collections.Counter()
        
        maxi = 1
        for n in arr:
            if n - difference in tail:
                maxi = max(maxi, tail[n-difference] + 1)
                tail[n] = tail[n-difference] + 1
            else:
                tail[n] = 1
            # print(tail, n, maxi)
        return maxi

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        count = Counter(arr)
        if difference == 0:
            return max(count.values())
        
        n = len(arr)
        dd = dict()
        ans = 1
        for i, n in enumerate(arr):
            if n-difference in dd:
                dd[n] = 1 + dd[n-difference]
            else:
                dd[n] = 1
            ans = max(ans, dd[n])
        # print(dd)
        return ans


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        mp = collections.defaultdict(int)
        ans = 0
        for a in arr:
            mp[a] = max(1+mp[a-difference], mp[a])
            ans = max(ans,mp[a])
        return ans


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        tail = collections.Counter()
        
        maxi = 1
        for n in arr:
            if n - difference in tail:
                maxi = max(maxi, tail[n-difference] + 1)
                tail[n] = tail[n-difference] + 1
            else:
                tail[n] = 1
        return maxi

from collections import defaultdict

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        prev_elem_dict = defaultdict(int)
        result = 0
        for num in arr:
            prev_elem_dict[num] = max(prev_elem_dict[num], prev_elem_dict[num - difference] + 1)
            result = max(result, prev_elem_dict[num])
        return result


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        a = len(arr)
        dp = {}
        ans = 0
        for value in arr:
            targetValue = value-difference
            if targetValue in dp:
                dp[value] = 1 + dp[targetValue]
            else:
                dp[value] = 1
                
            ans = max(ans, dp[value])
        return ans

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        num2len = dict()
        res = 0
        for i in range(len(arr)):
            if arr[i]-difference in num2len:
                num2len[arr[i]] = num2len[arr[i]-difference] + 1
            else:
                num2len[arr[i]] = 1
            
            res = max(res, num2len[arr[i]])
            
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        n = len(arr)
        ans = 1
        hmap = {arr[0]:1}
        for i in range(1, n):
            hmap[arr[i]] = 1
            if arr[i] - diff in hmap:
                hmap[arr[i]] = max(hmap[arr[i]], hmap[arr[i] - diff] + 1)
            ans = max(ans, hmap[arr[i]])
        # print(hmap)
        return ans


import bisect
class Solution:
    def longestSubsequence(self, arr, diff):
        ''' DP solution O(N^2)

        dp = [1]*len(arr)
        l_sub_seq = 1
        for i in range(1, len(arr)):
            for j in range(i):
                if arr[i] - arr[j] == diff:
                    dp[i] = max(dp[i], dp[j] + 1)
                    l_sub_seq = max(dp[i], l_sub_seq)
        return l_sub_seq
        '''
        dp = {}
        ans = 0
        for i in arr:
            if i - diff in dp:
                dp[i] = dp[i - diff] + 1
            else:
                dp[i] = 1
            ans = max(ans, dp[i])
        return ans


class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        res = {}
        for num in arr:
            res[num] = res.get(num-diff, 0) + 1
        return max(res.values())

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        n = len(arr)
        dp = dict()
        for i in range(n):
            if arr[i]-diff in dp:
                if arr[i] in dp:
                    dp[arr[i]] = max(dp[arr[i]],dp[arr[i]-diff]+1)
                else:
                    dp[arr[i]]=dp[arr[i]-diff]+1
            else:
                if arr[i] in dp:
                    dp[arr[i]] = max(dp[arr[i]],1)
                else:
                    dp[arr[i]]=1        
        # print(dp)
        return max(dp.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d , ans = defaultdict(int) , 0
        for i in arr:
            d[i] = d[i-difference] + 1
            ans = max(ans,d[i])
        return(ans)

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        dp, ans = dict(), 0
        for i in arr:
            dp[i] = dp.get(i-diff, 0) + 1
            ans = max(ans, dp[i])
        return ans

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = {}
        mx = 1

        for i, e in enumerate(arr):
            k = e + -difference

            if k in d:
                d[e] = d[k] + 1
                mx = max(mx, d[e])

            if e not in d:
                d[e] = 1

        return mx

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

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d={}
        res=0
        for i in arr:
            if i-difference in d:
                d[i]=1+d.pop(i-difference)
            elif i not in d:
                d[i]=1
            res=max(res,d[i])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        for a in arr:
            dp[a] = dp.get(a-difference, 0)+1
            
        return max(dp.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp=collections.defaultdict(int)
        ans=0
        for element in arr:
            dp[element]=dp[element-difference]+1
            ans=max(dp[element],ans)
        
        return ans

class Solution:
    def longestSubsequence(self, arr: List[int], d: int) -> int:
        
        if not arr:return 0
        maxlen=1
        helper={}
        
        for i,x in enumerate(arr):
            
            if x-d in helper:
                helper[x]=helper[x-d]+1
                
            else:
                helper[x]=1
                
            maxlen=max(maxlen,helper[x])
            
            
        return maxlen
            
        


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp, res = collections.defaultdict(int), 0
        for x in arr:
            dp[x] = max(1, dp[x])
            res = max(res, dp[x])
            dp[x+difference] = max(dp[x+difference], dp[x]+1)
        return res


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = {}

        for i, e in enumerate(arr):
            k = e + -difference

            if k in d:
                d[e] = d[k] + 1

            if e not in d:
                d[e] = 1

        return d[max(d, key=lambda k: d[k])]


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        states = collections.defaultdict(int)
        for a in arr:
            states[a] = states[a - difference] + 1
        return max(states.values())
            


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d={}
        res=0
        for i in arr:
            if i-difference in d:
                d[i]=max(1+d.pop(i-difference),d.get(i,0))
            elif i not in d:
                d[i]=1
            res=max(res,d[i])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        res = 1
        for i in arr:
            comp = i - difference
            if comp in dp:
                dp[i] = dp[comp] + 1
                res = max(res, dp[i])
            else:
                dp[i] = 1
        return res

from collections import defaultdict

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        currentMax = 0
        dictionary = defaultdict(int)
        for i in range(len(arr)):
            dictionary[arr[i]] = dictionary[arr[i]-difference] + 1
        for e in dictionary:
            currentMax = max(dictionary[e], currentMax)
        return currentMax


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if difference < 0:
            return self.longestSubsequence(arr[::-1], -difference)
        minim = 0
        for i in range(0, len(arr)):
            minim = min(arr[i], minim)
        maxim = arr[0]
        for i in range(0, len(arr)):
            arr[i] = arr[i] - minim
            maxim = max(maxim, arr[i])
        indices = [-1] * (maxim + difference + 1)
        dp = [0] * len(arr)
        i = len(arr) - 1
        while i >= 0:
            if indices[arr[i] + difference] != -1:
                dp[i] = 1 + dp[indices[arr[i] + difference]]
            else:
                dp[i] = 1
            indices[arr[i]] = i
            i = i - 1
        ans = -1
        for i in range(0, len(dp)):
            ans = max(ans, dp[i])
        return ans
            


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if len(arr)==1: return 1
        res,length = 1,len(arr)
        dp = {}
        dp[arr[-1]]=1
        flag = 1
        
        for i in range(length-2,-1,-1):
            if arr[i] not in dp: 
                dp[arr[i]] = 1
                flag = 0#means val was not in arr
            if arr[i]+difference in dp:
                if difference ==0 and flag ==0:
                    #if difference is 0 then i am seeing same no as arr[i] in dp and if flag is 0 then i already put its val in dp so should continue
                    flag = 1
                    continue
                dp[arr[i]] = max(dp[arr[i]], dp[arr[i]+difference]+1, )
            res = max(res,dp[arr[i]])
            
        return res


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


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        subseqs = dict()
        
        for num in arr:
            subseqs[num + difference] = subseqs.get(num, 0) + 1 
    
        return max(subseqs.values())
            


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

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        res = {}
        for num in arr:
            res[num] = res.get(num - difference,0) + 1
        return max(res.values())

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

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        #dp[i] longest subsequece at i
        dic = {}
        ans = 1
        for x in arr:
            pre = x - difference
            dic[x] = dic.get(pre, 0) + 1
            ans = max(ans, dic[x])
        return max(dic.values())


from collections import defaultdict

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        mapping = defaultdict(list)
        N = len(arr)
        for i in range(N):
            mapping[arr[i]].append(i)
        dp = [1]*N
        for i in range(1, N):
            curr = arr[i]
            if curr - difference in mapping:
                for idx in mapping[curr - difference]:
                    if idx >= i: break
                    if dp[idx] + 1 > dp[i]:
                        dp[i] = dp[idx] + 1
        return max(dp)

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        mp = {}
        ans = 0
        for n in arr:
            prev = mp.get(n,0)
            if n-diff in mp:
                mp[n] = mp[n-diff] + 1
            else:
                mp[n] = 1
            mp[n] = max(prev, mp[n])
            ans = max(ans, mp[n])
        return ans

class Solution:
    def longestSubsequence(self, arr: List[int], d: int) -> int:
        
        mp = {}
        
        for i,a in enumerate(arr):
            #print (mp,a)
            if a-d in mp:
                mp[a] = mp[a-d] + 1
            else:
                mp[a] = 1
        return max(mp.values())


from collections import Counter

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        max_len = 0
        dp = Counter()
        for i in range(len(arr)):
            dp[arr[i]] = max((dp[arr[i] - difference]) + 1, dp[arr[i]])
            max_len = max(max_len, dp[arr[i]])
        
        return max_len

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        max_len = 1
        for num in arr:
            dp[num] = max(dp.get(num, 1), 1 + dp.get(num - difference, 0))
            max_len = max(max_len, dp[num])
        return max_len

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

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

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        # dp
        max_len = 1
        dp = {}
        for a in arr:
            if a - difference in dp:
                dp[a] = dp[a - difference] + 1
                max_len = max(max_len, dp[a])
            else:
                dp[a] = 1
        return max_len

        # # brute force
        # max_len = 1
        # for i in range(len(arr)):
        #     curr_tail = arr[i]
        #     curr_len = 1
        #     for j in range(i + 1, len(arr)):
        #         if arr[j] - curr_tail == difference:
        #             curr_len += 1
        #             curr_tail = arr[j]
        #     max_len = max(max_len, curr_len)
        # return max_len



class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        d = dict()
        res = 1
        for i in arr:
            if i-diff in d.keys():
                d[i] = 1 + d[i-diff]
            else:
                d[i] = 1
            res = max(res, d[i])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        current = {}
        for x in arr:
            old = x - difference
            if old in current:
                count = current[old]
                del current[old]
                current[x] = count + 1
            elif x not in current:
                current[x] = 1
            #print(f'{x, current}')
        return max([x for x in list(current.values())])


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        record = collections.defaultdict(int)
        res = 0
        for i,v in enumerate(arr):
            l = 1
            if v - difference in record:
                l = record[v-difference]+1
            record[v] = l
            res = max(res,l)
        return res


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        # idea is similar to 300. Longest Increasing Subsequence
        # but instead of using a dp array and use nested for loop to
        # check condition, we can store the cur dp results in a hash map
        # so that we don't need a second for loop to check conditions.
        # dp = [1 for _ in range(len(arr))]
        # for i in range(len(dp)):
        #     for j in range(i):
        #         if arr[i]-arr[j] == difference:
        #             dp[i] = max(dp[i], 1+dp[j])
        # return max(dp)
        
        # stores the cur results of longest sequence
        dp = {}
        ans = 1
        for i in range(len(arr)):
            count = 1
            # update count for current if
            # condition is met
            if arr[i]-difference in dp:
                count += dp[arr[i]-difference]
            # store cur results
            dp[arr[i]] = count
            ans = max(ans, count)
        return ans

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        
        subseqs = dict()

        for num in arr:
            subseqs[num + difference] = subseqs.get(num, 0) + 1

        return max(subseqs.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        # DP
        if len(arr)==1: return 1
        d = {arr[0]:1}
        for i in range(1,len(arr)):
            if arr[i]-difference in d:
                d[arr[i]] = d[arr[i]-difference]+1
            else: # start a new sequence
                d[arr[i]] = 1
        return max(d.values())
                


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        _dict = {arr[0]:1}
        res = 1
        for i in arr[1:]:
            if i - difference in _dict:
                _dict[i] = 1 + _dict[i-difference]
                res = max(res, _dict[i])
            else:
                _dict[i] = 1
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        mi = min(arr)
        seq = [0] * (max(arr) - mi + 1)
        m = 0
        for a in arr:
            b = a - difference - mi
            v = 1
            if 0 <= b < len(seq):
                v += seq[b]
                seq[b] = 0
            seq[a - mi] = max(seq[a - mi], v)
            m = max(m, seq[a - mi])
        return m

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        record = {}
        for i in range(len(arr)):
            a = arr[i]
            if a - difference in record:
                record[a] = record[a - difference] + 1
            else:
                record[a] = 1

        return max(list(record.values()))

class Solution:
    def longestSubsequence(self, arr: List[int], diff: int) -> int:
        d = dict()
        res = 1
        for i in arr:
            t = 0
            try:
                t = d[i-diff]
            except:
                pass
            if t:
                d[i] = 1 + d[i-diff]
            else:
                d[i] = 1
            res = max(res, d[i])
        return res

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        seq = {}
        for a in arr:
            seq[a] = max(seq.get(a, 0), seq.pop(a - difference, 0) + 1)
        return max(seq.values())

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        from collections import defaultdict
        indexMap = defaultdict(list)
        for i in range(len(arr)-1, -1, -1):
            indexMap[arr[i]].append(i)
            
        dp = [1] * (len(arr))
        maxLen = 1
        for i in range(len(arr)):
            indexMap[arr[i]].pop()
            nextVal = arr[i] + difference
            if nextVal in indexMap and indexMap[nextVal]:
                j = indexMap[nextVal][-1]
                dp[j] = max(dp[i] + 1, dp[j])
                maxLen = max(maxLen, dp[j])
        return maxLen

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d=collections.defaultdict(int)
        res=0
        for i in arr:
            if i-difference in d:
                d[i]=1+d.pop(i-difference)
            elif i not in d:
                d[i]=1
            res=max(res,d[i])
        return res