Problem Description

The Longest Arithmetic Subsequence problem asks you to find the length of the longest arithmetic subsequence within a given array of integers nums.

• An arithmetic subsequence is a sequence of numbers where the difference between every two consecutive elements is the same (for example, [3, 5, 7, 9] has a difference of 2).
• You can pick any subset of elements from nums (not necessarily consecutive), but you must keep their original order.
• The task is to return the length of the longest possible arithmetic subsequence.
• Constraints: Each element can only be used once in the subsequence, and you must not reorder elements.

Example: For nums = [3, 6, 9, 12], the answer is 4 because the whole array forms an arithmetic sequence with difference 3.

Thought Process

At first glance, you might think about checking every possible subsequence to see if it's arithmetic, but this would be extremely inefficient because the number of subsequences grows exponentially with the length of the array.

Instead, we can optimize by noticing that for any two elements, they can form the start of an arithmetic sequence with a particular difference. If we keep track of the longest arithmetic subsequence ending at each position with each possible difference, we can build up the solution efficiently.

• Brute-force: Try all subsequences (too slow).
• Optimized: Use dynamic programming to record, for each index and difference, the length of the longest arithmetic subsequence ending there.

This shift in thinking—from generating all subsequences to tracking differences—makes the problem tractable.

Solution Approach

We'll use a dynamic programming approach with hash maps.

1. For each index i in nums, maintain a hash map dp[i] where the keys are differences and the values are the length of the longest arithmetic subsequence ending at i with that difference.
2. For each pair of indices (j, i) with j < i, calculate the difference diff = nums[i] - nums[j].
3. If dp[j] already has a subsequence with difference diff, then dp[i][diff] = dp[j][diff] + 1. Otherwise, start a new sequence of length 2 (using nums[j] and nums[i]).
4. Track the maximum length found across all dp[i] entries.

We use hash maps for dp[i] because the range of possible differences can be large and negative, and hash maps allow fast lookups and updates.

Example Walkthrough

Let's use nums = [9, 4, 7, 2, 10].

• Start with empty maps for each index: dp = [{}, {}, {}, {}, {}].
• For i = 1 (nums[1] = 4), compare to j = 0:
  • diff = 4 - 9 = -5. No previous sequence, so dp[1][-5] = 2.
• For i = 2 (nums[2] = 7), compare to j = 0, 1:
  • j = 0: diff = 7 - 9 = -2 → dp[2][-2] = 2.
  • j = 1: diff = 7 - 4 = 3 → dp[2][3] = 2.
• For i = 3 (nums[3] = 2), compare to j = 0, 1, 2:
  • j = 0: diff = 2 - 9 = -7 → dp[3][-7] = 2.
  • j = 1: diff = 2 - 4 = -2 → dp[3][-2] = 2.
  • j = 2: diff = 2 - 7 = -5 → dp[3][-5] = 2.
• For i = 4 (nums[4] = 10), compare to j = 0, 1, 2, 3:
  • j = 0: diff = 10 - 9 = 1 → dp[4][1] = 2.
  • j = 1: diff = 10 - 4 = 6 → dp[4][6] = 2.
  • j = 2: diff = 10 - 7 = 3. dp[2][3] = 2 so dp[4][3] = 3.
  • j = 3: diff = 10 - 2 = 8 → dp[4][8] = 2.
• The longest found is length 3: [4, 7, 10] (difference 3).

The answer is 3.

Time and Space Complexity

• Brute-force: Checking all subsequences is O(2^n) time and space, which is infeasible for large n.
• Optimized DP: For each pair of indices (i, j), we do constant work. There are O(n^2) such pairs, so time complexity is O(n^2).
• Space Complexity: We store a hash map for each index, each with up to O(n) entries (in the worst case), so total space is O(n^2).

Summary

By focusing on differences and using dynamic programming with hash maps, we efficiently find the longest arithmetic subsequence in O(n^2) time and space. The key insight is to track, for each index and difference, the length of the sequence ending there—building longer sequences from shorter ones as we progress through the array.

Code Implementation

from collections import defaultdict

class Solution:
    def longestArithSeqLength(self, nums):
        n = len(nums)
        if n <= 1:
            return n
        dp = [defaultdict(int) for _ in range(n)]
        max_len = 2
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                if diff in dp[j]:
                    dp[i][diff] = dp[j][diff] + 1
                else:
                    dp[i][diff] = 2
                max_len = max(max_len, dp[i][diff])
        return max_len
      

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int longestArithSeqLength(std::vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        std::vector<std::unordered_map<int, int>> dp(n);
        int maxLen = 2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int diff = nums[i] - nums[j];
                int len = 2;
                if (dp[j].count(diff)) {
                    len = dp[j][diff] + 1;
                }
                dp[i][diff] = std::max(dp[i][diff], len);
                maxLen = std::max(maxLen, dp[i][diff]);
            }
        }
        return maxLen;
    }
};
      

import java.util.*;

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = new HashMap<>();
        }
        int maxLen = 2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int diff = nums[i] - nums[j];
                int len = dp[j].getOrDefault(diff, 1) + 1;
                dp[i].put(diff, Math.max(dp[i].getOrDefault(diff, 0), len));
                maxLen = Math.max(maxLen, dp[i].get(diff));
            }
        }
        return maxLen;
    }
}
      

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestArithSeqLength = function(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    const dp = Array.from({length: n}, () => new Map());
    let maxLen = 2;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            const diff = nums[i] - nums[j];
            const len = (dp[j].get(diff) || 1) + 1;
            dp[i].set(diff, Math.max(dp[i].get(diff) || 0, len));
            maxLen = Math.max(maxLen, dp[i].get(diff));
        }
    }
    return maxLen;
};