Longest Arithmetic Subsequence

Medium
870.

Longest Arithmetic Subsequence

Longest Arithmetic Subsequence is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestArithSeqLength = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Longest Arithmetic Subsequence

  1. Hint 1

    A subsequence is pinned down by its last element and its common difference.

  2. Hint 2

    dp[i][d] is the length of the longest arithmetic subsequence ending at index i with difference d.

  3. Hint 3

    Extend from every earlier index: dp[i][d] = dp[j][d] + 1 where d = 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

  1. For each i, loop over every j < i and compute d = nums[i] - nums[j].
  2. Set dp[i][d] = (dp[j][d] or 1) + 1 — the or 1 treats nums[j] alone as a length-1 chain.
  3. 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

Java

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