Longest Arithmetic Subsequence — Medium Problem & Solution

Return the length of the longest arithmetic subsequence of nums — a subsequence whose consecutive differences are all equal.

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 <= 1000
0 <= nums[i] <= 500

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 every j < i and compute d = nums[i] - nums[j].
Set dp[i][d] = (dp[j][d] or 1) + 1 — the or 1 treats nums[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] + 1 without 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue