1218. Longest Arithmetic Subsequence of Given Difference

1. Description

For an integer array arr and an integer difference, find the greatest possible length of a subsequence whose consecutive elements differ by exactly difference, subtracting the earlier element from the later one.
Elements may be skipped when choosing the subsequence, but their original relative order must remain unchanged.

2. Example

Example 1

Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: All four elements form a valid subsequence, increasing by 1 at each step.

Example 2

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: No two elements can form the required difference, so the best choice contains one element.

Example 3

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: Choosing [7,5,3,1] gives four elements with a difference of -2 between consecutive values.

3. Constraints

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

4. Solutions

Dynamic Programming

n = arr.size()
Time complexity: O(n) on average
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int longestSubsequence(const vector<int> &arr, int difference) {
        unordered_map<int, int> length_by_value;
        int max_length = 1;

        for (int num : arr) {
            if (length_by_value.contains(num - difference)) {
                length_by_value[num] = length_by_value[num - difference] + 1;

                max_length = max(max_length, length_by_value[num]);
            } else {
                length_by_value[num] = 1;
            }
        }

        return max_length;
    }
};