Longest Arithmetic Subsequence: DP with Hash Map Pattern

Given an array of integers nums, return the length of the longest arithmetic subsequence in nums. A subsequence is a sequence that can be derived by deleting some or no elements without changing the order of the remaining elements. An arithmetic subsequence is one where the difference between consecutive elements is constant.

This is LeetCode 1027: Longest Arithmetic Subsequence, a medium-difficulty problem that combines pairwise dynamic programming with hash maps. It is a natural extension of the classic Longest Increasing Subsequence problem, but instead of tracking "is this value bigger?", you track "does this value continue a specific arithmetic pattern?"

Why this problem matters

The longest arithmetic subsequence problem teaches you a DP technique that goes beyond simple single-value state. In LIS, each index stores one number: the length of the longest increasing subsequence ending there. Here, each index needs to store multiple lengths, one for every possible common difference. That forces you to use a hash map at each index, and that pattern shows up across many interview problems.

This problem also reinforces pairwise thinking. For every pair (j, i) where j is before i, you compute a difference and ask: "Is there already a subsequence ending at j with this exact difference?" If yes, extend it. If no, start a new pair. That scan-and-extend logic is the same skeleton you see in LIS, but the state space is richer.

Once you internalize this pattern, you can apply it to problems like Longest Arithmetic Subsequence of Given Difference (LeetCode 1218), Number of Longest Increasing Subsequences (LeetCode 673), and any problem where the DP state needs a secondary key beyond just the index.

The key insight

For each index i, maintain a dictionary dp[i] that maps each common difference d to the length of the longest arithmetic subsequence ending at index i with that difference. For each pair (j, i) where j is before i, compute the difference d = nums[i] - nums[j]. Then:

• If dp[j] already has an entry for d, that means there is an arithmetic subsequence ending at j with difference d. You can extend it by appending nums[i], so dp[i][d] = dp[j][d] + 1.
• If dp[j] does not have an entry for d, then (nums[j], nums[i]) is a new pair of length 2, so dp[i][d] = 2.

The answer is the maximum value across all dp[i] dictionaries.

The solution

def longest_arith_seq_length(nums):
    n = len(nums)
    dp = [{} for _ in range(n)]
    result = 2

    for i in range(1, n):
        for j in range(i):
            d = nums[i] - nums[j]
            dp[i][d] = dp[j].get(d, 1) + 1
            result = max(result, dp[i][d])

    return result

The outer loop picks each index i as the potential end of a subsequence. The inner loop scans every earlier index j to form a pair. For each pair, you compute the difference d and look up whether j already has an arithmetic subsequence with that difference. The .get(d, 1) call returns 1 if there is no existing entry, because nums[j] alone is a subsequence of length 1. Adding nums[i] makes it length 2.

The variable result tracks the global maximum across all indices and all differences.

Visual walkthrough

In the walkthrough above, the critical moment is when we process index 4 (value 10) and check index 2 (value 7). The difference is 3, and dp[2][3] = 2 because we previously found the pair (4, 7) with difference 3. So dp[4][3] = 2 + 1 = 3, giving us the subsequence [4, 7, 10]. That is the longest arithmetic subsequence in the array.

Complexity analysis

Time: O(n^2). The nested loops check every pair (j, i). Each dictionary lookup and update is O(1) on average.

Space: O(n^2). In the worst case, each of the n indices could store up to n - 1 different differences in its dictionary. For example, if all elements are distinct, the total number of entries across all dictionaries is O(n^2).

There is no known way to solve this problem faster than O(n^2) in the general case, because you genuinely need to consider all pairs.

The building blocks

1. Pairwise DP with hash map

The core pattern is: for each pair (j, i), compute a key (the difference) and use it to extend or start a subsequence. The hash map at each index lets you track multiple "threads" of subsequences simultaneously.

for i in range(1, n):
    for j in range(i):
        d = nums[i] - nums[j]
        dp[i][d] = dp[j].get(d, 1) + 1

This pattern generalizes beyond arithmetic sequences. Any time you need to track subsequences with a specific relationship between consecutive elements, a dictionary keyed by that relationship is the right structure.

2. Common difference tracking

The dictionary at each index partitions subsequences by their common difference. This avoids the combinatorial explosion of tracking every individual subsequence. You only need to know, for each (index, difference) pair, the length of the longest subsequence ending there.

d = nums[i] - nums[j]
length_so_far = dp[j].get(d, 1)
dp[i][d] = length_so_far + 1

This "partition by a secondary key" idea appears in many DP problems. Whenever the transition depends on more than just the index, add a secondary key to your state.

Edge cases

• Array of length 2: any two elements form an arithmetic subsequence. The answer is always 2.
• All elements identical: e.g., [5, 5, 5, 5]. The common difference is 0, and the entire array is an arithmetic subsequence. The answer is n.
• Strictly increasing with constant difference: e.g., [1, 3, 5, 7]. The whole array is the answer. The DP naturally captures this.
• Large negative differences: e.g., [100, 50, 0, -50]. Differences can be negative. The hash map handles this without any special logic.
• Multiple subsequences of the same max length: the problem only asks for the length, not the actual subsequence, so you just track the maximum.

From understanding to recall

You have just walked through the complete DP with hash map solution for Longest Arithmetic Subsequence. The idea is clean: for every pair, compute a difference, look up whether that difference has been seen before at the earlier index, and extend or start a new chain. The hash map at each index is what makes it work.

But reading through it once is not enough for interview readiness. You need to be able to write the nested loop, set up the dictionary, and handle the .get(d, 1) default without hesitation. That takes repetition. Spaced repetition, specifically, where you revisit this problem at increasing intervals until the pattern is automatic.

This problem is one instance of a broader family: "pairwise DP with a secondary key." Once that pattern is in your long-term memory, you will recognize it instantly in problems like Longest Arithmetic Subsequence of Given Difference, Number of Longest Increasing Subsequences, and Arithmetic Slices II. Drilling the building blocks individually is far more efficient than grinding random problems.

Related posts

• Longest Increasing Subsequence - classic subsequence DP
• Arithmetic Slices - arithmetic patterns in contiguous subarrays
• Longest Common Subsequence - another pairwise DP approach

Longest Arithmetic Subsequence is a perfect example of how a small twist on a classic pattern (adding a hash map to LIS-style DP) opens up a whole new category of problems. If you want to build these patterns into your long-term memory so they are ready on interview day, spaced repetition is the fastest path.