LeetCode 1027: Longest Arithmetic Subsequence

Problem Restatement

We are given an integer array nums.

We need to return the length of the longest arithmetic subsequence in nums.

A subsequence is arithmetic if the difference between consecutive elements is constant.

The official constraints state that 2 <= nums.length <= 1000 and 0 <= nums[i] <= 500.

Input and Output

Function shape:

def longestArithSeqLength(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 6, 9, 12]

The whole array is arithmetic with difference 3.

Answer:

4

Example 2:

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

Subsequence [4, 7, 10] with difference 3.

Answer:

3

Example 3:

nums = [20, 1, 15, 3, 10, 5, 8]

Subsequence [20, 15, 10, 5] with difference -5.

Answer:

4

Key Insight

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

For each pair (j, i) with j < i:

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

Algorithm

1. Create dp as a list of dictionaries.
2. For each index i, for each j < i:
   • Compute d = nums[i] - nums[j].
   • dp[i][d] = dp[j].get(d, 1) + 1.
3. Track the maximum value across all dp[i][d].

Correctness

dp[j].get(d, 1) returns the length of the best arithmetic subsequence ending at j with difference d, or 1 if no such subsequence exists (just the single element nums[j]). Adding 1 accounts for nums[i].

By considering all pairs, every possible arithmetic subsequence is captured.

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        dp = [{} for _ in range(len(nums))]
        best = 2

        for i in range(1, len(nums)):
            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

Testing

def run_tests():
    s = Solution()

    assert s.longestArithSeqLength([3, 6, 9, 12]) == 4
    assert s.longestArithSeqLength([9, 4, 7, 2, 10]) == 3
    assert s.longestArithSeqLength([20, 1, 15, 3, 10, 5, 8]) == 4
    assert s.longestArithSeqLength([0, 8, 45, 88, 48, 68, 28, 55, 17, 24]) == 2

    print("all tests passed")

run_tests()