Longest Arithmetic Subsequence — DP Tables Powered by Hash Maps

Problem Statement#

Given an integer array nums, return the length of the longest arithmetic subsequence in nums. A sequence is arithmetic if consecutive elements share the same difference. A subsequence preserves order but does not need to be contiguous.

Constraints:

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

Input:  nums = [3,6,9,12]
Output: 4

Input:  nums = [9,4,7,2,10]
Output: 3

Why This Problem Matters#

LeetCode 1027 sits at the intersection of two interview pillars: dynamic programming and hashmap interview design. Google, Amazon, and Microsoft love it because the candidate must define a state, justify the transition, and pick the right data structure to make the transition cheap. The "right" data structure here is a hashmap per index, keyed by common difference.

If a candidate writes a 1D DP, they will discover the state is too thin and fail to extend short subsequences correctly. If they write a 2D table indexed by (i, diff) with an integer offset, they will get a working answer but show less hash-table fluency. The hashmap-of-hashmap solution is the canonical FAANG answer because it generalizes to negative numbers, large absolute values, and sparse difference distributions.

The hash table FAANG signal here: can you nest a hashmap inside a DP table without losing your footing?

The Core Insight#

For every pair (i, j) with i < j, the difference d = nums[j] - nums[i] defines a candidate arithmetic subsequence ending at j. If we already know the longest subsequence ending at i with difference d, we can extend it by 1 to land at j. Maintain dp[j][d] as a hashmap and the recurrence becomes dp[j][d] = dp[i][d] + 1.

Visual Dry Run#

nums = [9,4,7,2,10].

Best length seen: 3, formed by [4, 7, 10].

Solution (Optimal)#

class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [dict() for _ in range(n)]
        best = 2
        for j in range(1, n):
            for i in range(j):
                d = nums[j] - nums[i]
                dp[j][d] = dp[i].get(d, 1) + 1
                if dp[j][d] > best:
                    best = dp[j][d]
        return best

var longestArithSeqLength = function(nums) {
    const n = nums.length;
    const dp = Array.from({length: n}, () => new Map());
    let best = 2;
    for (let j = 1; j < n; j++) {
        for (let i = 0; i < j; i++) {
            const d = nums[j] - nums[i];
            const prev = dp[i].get(d) || 1;
            dp[j].set(d, prev + 1);
            if (dp[j].get(d) > best) best = dp[j].get(d);
        }
    }
    return best;
};

Time: O(n^2) — every pair (i, j) is processed once with O(1) hashmap operations. Space: O(n^2) — each of the n hashmaps can hold up to n distinct differences.

Common Mistakes#

• Initializing dp[i][d] to 0 instead of 1, which makes a single element worth nothing and produces lengths off by one.
• Iterating j before i in the outer loop, breaking the dependency that dp[i] must be filled before dp[j].
• Using a single shared hashmap across all indices, losing the "per index" isolation the recurrence needs.
• Trying a 1D DP without a difference dimension and missing the recurrence.
• Returning best before initializing it to at least 2 in the edge case n = 2.

Interview Tips#

• State the recurrence aloud: dp[j][d] = dp[i][d] + 1. Interviewers love watching candidates discover this in real time.
• Mention the offset-array alternative, then justify hashmaps for arbitrary value ranges.
• Note that the answer is always at least 2, because any pair forms an arithmetic sequence.
• Mention space optimization is hard here, then move on; this is a hashmap fluency problem, not a memory problem.

Follow-up Questions#

• What if differences must be a fixed value d? Hint: that is LeetCode 1218, solvable in O(n) with a single hashmap.
• What if the array is a stream? Hint: maintain dp lazily indexed by value last seen, refresh on each new element.
• What if you need to return the actual subsequence? Hint: store the predecessor index in a parallel hashmap.
• What if the input contains floats? Hint: hash differences with caution; floating point equality is unreliable.
• Can you do better than O(n^2)? Hint: not in the worst case for arbitrary integers; this is a known lower bound.

Key Takeaways#

• LeetCode 1027 is a FAANG-grade fusion of DP and hashmap interview design.
• The state dp[j][d] is a hashmap per index, keyed by common difference.
• Initialize dp[i][d] to 1 so the recurrence accounts for the starting element.
• Time is O(n^2), space is O(n^2) — both unavoidable for this problem.
• Hashmaps generalize this DP to any integer range without offset arithmetic.
• The pattern reappears in Longest Geometric Subsequence and Longest Fibonacci Subsequence.
• Recognize "subsequence with constant pairwise property" as the trigger for this DP-plus-hashmap shape.