Longest Arithmetic Subsequence of Given Difference
Medium · Dynamic Programming · Array · Hash Table · Dynamic Programming
Problem
You are given an integer array arr and an integer difference.
Return the length of the longest subsequence of arr in which every element minus the element before it equals exactly difference. A subsequence keeps the original order of the elements it uses, but may skip any of the others. A single element is a valid subsequence of length 1.
Examples
Input: arr = [1,5,2,9,3,4], difference = 1 Output: 4
1, 2, 3, 4 rises by exactly 1 each step, skipping 5 and 9.
Input: arr = [6,4,2,0], difference = -2 Output: 4
The whole array steps down by 2.
Input: arr = [1,2,3], difference = 5 Output: 1
No two elements differ by 5, so the best is one element on its own.
Constraints
- 1 <= len(arr) <= 10^5
- -10^4 <= arr[i], difference <= 10^4
Approaches
- Quadratic DP over earlier indices — time O(n²), space O(n)
Follow-up
What if the difference is not given, and you want the longest arithmetic subsequence with any common difference? Then each element must remember a chain length per difference: a map per index, filled from every earlier index, O(n²) time. The fixed difference is what makes one map enough.
Related problems
Start free on Cariara · Coding problems · System design studio
