Longest Arithmetic Subsequence of Given Difference Solution
Longest Arithmetic Subsequence of Given Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Arithmetic Subsequence of Given Difference is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array arr and an integer difference, return the length of the longest subsequence in arr that is an arithmetic sequence with that exact common difference.
A subsequence keeps the relative order of the remaining elements but need not be contiguous.
Example 1
Input: arr = [1,2,3,4], difference = 1
Output: 4
Example 2
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: No two elements differ by exactly 1.
Example 3
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The subsequence [7,5,3,1].
Constraints
1 <= arr.length <= 40-1000 <= arr[i], difference <= 1000
Hints for Longest Arithmetic Subsequence of Given Difference
Hint 1
Any such subsequence is determined by its last element — you never need to look further back than one step.
Hint 2
Keep a map from value to the longest chain ending at that value.
Hint 3
Reading
map[x - difference]while processingxextends the chain in O(1).
How to solve Longest Arithmetic Subsequence of Given Difference
A chain with fixed difference is determined by its last value, so keep a map from value to the longest chain ending there and extend from x - difference.
Approach
- For each
x, setbest[x] = best.get(x - difference, 0) + 1. - Track the maximum.
Why it works
The element before x in any valid chain must be exactly x - difference, so the longest chain ending at x is one more than the longest ending at that predecessor seen so far.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Later copies of
xoverwritebest[x]with a value at least as large, which is what you want. - A difference of 0 works unchanged — chains of equal values.
Reference solution
Python
def longestSubsequence(arr, difference: int) -> int:
best = {}
answer = 0
for x in arr:
best[x] = best.get(x - difference, 0) + 1
answer = max(answer, best[x])
return answerJava
public static int longestSubsequence(int[] arr, int difference) {
Map<Integer, Integer> best = new HashMap<>();
int answer = 0;
for (int x : arr) {
int len = best.getOrDefault(x - difference, 0) + 1;
best.put(x, len);
if (len > answer) answer = len;
}
return answer;
}C++
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int, int> best;
int answer = 0;
for (int x : arr) {
int len = 1;
auto it = best.find(x - difference);
if (it != best.end()) len = it->second + 1;
best[x] = len;
answer = max(answer, len);
}
return answer;
}JavaScript
var longestSubsequence = function(arr, difference) {
const best = new Map();
let answer = 0;
for (let i = 0; i < arr.length; i++) {
const prev = best.get(arr[i] - difference) || 0;
const len = prev + 1;
best.set(arr[i], len);
if (len > answer) answer = len;
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets