Formatted question description: https://leetcode.ca/all/1218.html
1218. Longest Arithmetic Subsequence of Given Difference
Level
Medium
Description
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
Solution
Use dynamic programming. Create an array subLengths
of length arr.length
, where subLengths[i]
represents the length of the longest arithmetic subsequence with difference difference
that ends at index i
. Use a map to store each number and the last index that the number occurs. Initially, set subLengths[0] = 1
and put the keyvalue pair (arr[0], 0)
into the map.
Loop over arr
starting from index 1. At each index i
, obtain the number at index i
and the previous number in the arithmetic subsequence. If the previous number exists in the key set of the map, then obtain the previous number’s index prevIndex
and the previous subsequence length subLengths[prevIndex]
, set subLengths[i] = subLengths[prevIndex] + 1
, and update the maximum length of arithmetic subsequence as well. If the previous number does not exist in the key set of the map, then simply set subLengths[i] = 1
. For each index i
, put the keyvalue pair (arr[i], i)
into the map.
Finally, return the maximum length of arithmetic subsequence.

class Solution { public int longestSubsequence(int[] arr, int difference) { int length = arr.length; int[] subLengths = new int[length]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); subLengths[0] = 1; map.put(arr[0], 0); int max = 1; for (int i = 1; i < length; i++) { int num = arr[i]; int prevNum = num  difference; if (map.containsKey(prevNum)) { int prevIndex = map.get(prevNum); subLengths[i] = subLengths[prevIndex] + 1; max = Math.max(max, subLengths[i]); } else subLengths[i] = 1; map.put(num, i); } return max; } }

// OJ: https://leetcode.com/problems/longestarithmeticsubsequenceofgivendifference/ // Time: O(N) // Space: O(N) class Solution { public: int longestSubsequence(vector<int>& A, int difference) { unordered_map<int, int> m; int ans = 0; for (int n : A) { int prev = n  difference; if (m.count(prev)) { m[n] = m[prev] + 1; if (n != prev) m.erase(prev); } else if (m.count(n) == 0) m[n] = 1; ans = max(ans, m[n]); } return ans; } };

# 1218. Longest Arithmetic Subsequence of Given Difference # https://leetcode.com/problems/longestarithmeticsubsequenceofgivendifference/ class Solution: def longestSubsequence(self, arr: List[int], difference: int): mp = collections.defaultdict(int) for num in arr: mp[num] = 1 if num  difference not in mp else mp[numdifference] + 1 return max(mp.values())