Longest Arithmetic Subsequence — Problem & Solution
Longest Arithmetic Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Arithmetic Subsequence is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming, Binary Search
- Asked at: Amazon, Google, Adobe
- 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
Return the length of the longest arithmetic subsequence of nums — a subsequence whose consecutive differences are all equal. A subsequence of length 1 or 2 is always arithmetic.
Example 1
Input: nums = [3,6,9,12]
Output: 4
Explanation: The whole array has common difference 3.
Example 2
Input: nums = [9,4,7,2,10]
Output: 3
Explanation: [4,7,10] has difference 3.
Example 3
Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation: [20,15,10,5] has difference -5.
Constraints
2 <= nums.length <= 10000 <= nums[i] <= 500
Hints for Longest Arithmetic Subsequence
Hint 1
A subsequence is pinned down by its last element and its common difference.
Hint 2
dp[i][d]is the length of the longest arithmetic subsequence ending at indexiwith differenced.Hint 3
Extend from every earlier index:
dp[i][d] = dp[j][d] + 1whered = nums[i] - nums[j].
How to solve Longest Arithmetic Subsequence
State the DP on (last index, common difference). Since the difference is fixed once two elements are chosen, every pair (j, i) extends exactly one chain.
Approach
- For each
i, loop over everyj < iand computed = nums[i] - nums[j]. - Set
dp[i][d] = (dp[j][d] or 1) + 1— theor 1treatsnums[j]alone as a length-1 chain. - Track the maximum over all states.
Why it works
Any arithmetic subsequence of length at least 2 has a well-defined difference, and its longest extension ending at i must come from its previous element j. So the recurrence is exhaustive. The or 1 base case is what makes a pair count as length 2.
Complexity
- Time —
O(n²) - Space —
O(n²) in the worst case
Pitfalls
- Differences can be negative, so a plain array needs an offset (values are at most 500, so the range is
[-500, 500]). - The base for a fresh pair is 2, not 1 — that is what
dp[j][d]defaulting to 1 encodes. - Taking
dp[j][d] + 1without the default under-counts every two-element chain.
Reference solution
Python
from typing import List
def longestArithSeqLength(nums: List[int]) -> int:
n = len(nums)
dp = [dict() for _ in range(n)]
best = 1
for i in range(n):
for j in range(i):
d = nums[i] - nums[j]
dp[i][d] = dp[j].get(d, 1) + 1
best = max(best, dp[i][d])
return bestJava
public static int longestArithSeqLength(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][1001];
int best = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j] + 500;
int prev = dp[j][d] == 0 ? 1 : dp[j][d];
dp[i][d] = prev + 1;
best = Math.max(best, dp[i][d]);
}
}
return best;
}C++
int longestArithSeqLength(vector<int>& nums) {
int n = (int) nums.size();
vector<vector<int>> dp(n, vector<int>(1001, 0));
int best = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j] + 500;
int prev = dp[j][d] == 0 ? 1 : dp[j][d];
dp[i][d] = prev + 1;
best = max(best, dp[i][d]);
}
}
return best;
}JavaScript
var longestArithSeqLength = function(nums) {
var n = nums.length;
if (n <= 1) return n;
var dp = [];
var best = 1;
for (var i = 0; i < n; i++) {
dp.push({});
for (var j = 0; j < i; j++) {
var d = nums[i] - nums[j];
var prev = dp[j][d] || 1;
dp[i][d] = prev + 1;
if (dp[i][d] > best) best = dp[i][d];
}
}
return best;
};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