Longest Arithmetic Subsequence of Given Difference
Find the longest subsequence where each value is exactly a fixed difference more than the one before it. A one-pass dynamic programming problem keyed by value instead of index. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array arr and an integer difference. Find the length of the longest subsequence of arr in which every element minus the element right before it equals difference.
A subsequence keeps the original left-to-right order but may skip elements. A single element on its own is a valid subsequence of length 1.
Example 1
- Input
- arr = [2, 5, 8, 4, 11, 14], difference = 3
- Output
- 5
Take 2, 5, 8, 11, 14 and skip the 4.
Example 2
- Input
- arr = [7, 7, 7, 3, 7], difference = 0
- Output
- 4
The four 7s form a subsequence where each step adds 0.
Example 3
- Input
- arr = [9, 6, 3, 0, 1], difference = -3
- Output
- 4
9, 6, 3, 0 steps down by 3 each time.
Constraints
- 1 ≤ arr.length ≤ 10⁵
- -10⁴ ≤ arr[i], difference ≤ 10⁴
- The answer is at least 1.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Longest Arithmetic Subsequence of Given Difference in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Longest Arithmetic Subsequence of Given Difference
Pattern: DP in a hash map keyed by value
Since the difference is fixed, the element that comes right before x in a valid subsequence must be exactly x - difference. There's no choice to make about which predecessor, only whether one has appeared earlier.
So define best[v] as the length of the longest valid subsequence seen so far that ends with value v. When you reach x, it can extend the best chain ending at x - difference: best[x] = best[x - difference] + 1, or 1 if there is none. Processing left to right guarantees that any chain you extend came from earlier elements.
Approach 1: Index DP over all earlier elements
Let dp[i] be the longest chain ending at index i. For each i, look at every j < i with arr[i] - arr[j] == difference and take dp[j] + 1. Correct, but every element scans everything before it.
Time O(n²) · Space O(n)
Approach 2: Hash map keyed by ending value
- Start with an empty map
best. - For each
xin order, setbest[x] = best.get(x - difference, 0) + 1. - Track the largest value written and return it.
If the same value appears again later, overwriting best[x] is safe: the later occurrence's chain is at least as long, since it could have used everything the earlier one did.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Index DP over all earlier elements | O(n²) | O(n) |
| Hash map keyed by ending value | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Longest Arithmetic Subsequence of Given Difference solution in Python
def longest_subsequence(arr: list[int], difference: int) -> int:
best = {} # value -> longest chain ending with that value
answer = 0
for x in arr:
length = best.get(x - difference, 0) + 1
best[x] = length
answer = max(answer, length)
return answerLongest Arithmetic Subsequence of Given Difference solution in JavaScript
function longestSubsequence(arr, difference) {
const best = new Map(); // value -> longest chain ending with that value
let answer = 0;
for (const x of arr) {
const length = (best.get(x - difference) ?? 0) + 1;
best.set(x, length);
answer = Math.max(answer, length);
}
return answer;
}Common mistakes
- Looking up `x + difference` instead of `x - difference`. The predecessor is the smaller step back.
- Sorting the array first. A subsequence has to keep the original order.
- Mishandling difference = 0, where the answer is the count of the most frequent value. The map handles it if you read before you write.
- Returning the value of the last entry instead of the maximum over all entries.
What interviewers look for
Point out what makes this easier than the general Longest Arithmetic Subsequence: the difference is given, so each element has exactly one possible predecessor value. That's the reason a value-keyed map replaces the O(n²) inner loop.
Talk through the duplicate case. Interviewers often ask "what happens when the same value shows up twice?" and want to hear why overwriting is correct.
Follow-up questions
What if the difference is not given and you need the longest arithmetic subsequence for any difference?
Keep a map per index: dp[i][d] is the longest chain ending at index i with difference d. For each pair j < i, set dp[i][arr[i] - arr[j]] = dp[j].get(d, 1) + 1. That costs O(n²) time and space.
How would you return the subsequence itself?
Store, along with each length, the index of the element it extended. After the scan, start from the index with the largest length and follow those links back, then reverse.
If values are in a small known range, can you avoid hashing?
Yes. Use an array indexed by value minus the minimum value. Lookups become plain array reads and the space is the size of the value range.
Companies that ask Longest Arithmetic Subsequence of Given Difference
Longest Arithmetic Subsequence of Given Difference is tagged by 89 companies in our interview dataset. The score shows how often it comes up at each company.
- Arm100%
- Monzo100%
- Weedmaps100%
- Diasorin100%
- Darktrace97%
- Astera Labs95%
- Peraton93%
- Highradius92%
- General Dynamics Mission Systems91%
- Adidas87%
- Cummins84%
- Sumup83%
- Gft Group83%
- Dynatrace83%
- Procore Technologies81%
- Freshbooks81%
- Beam Therapeutics80%
- GitHub79%
- Mixi78%
- Philips78%
- Swisscom77%
- Just Eat74%
- Wepay74%
- Egen74%
and 65 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required