Problem Description

You are given an array nums of integers. Your task is to find the length of the longest arithmetic subsequence that can be formed from this array.

An arithmetic subsequence is a sequence where the difference between consecutive elements is constant. For example, [3, 7, 11, 15] is arithmetic because each pair of consecutive elements has a difference of 4.

A subsequence is derived from the original array by deleting some or no elements while maintaining the relative order of the remaining elements. For instance, from array [1, 3, 5, 7, 9], we can form subsequence [1, 5, 9] by removing elements at positions 1 and 3.

The solution uses dynamic programming with a 2D array f[i][j] where:

• i represents the index of the current element in nums
• j represents the common difference (offset by 500 to handle negative differences)
• f[i][j] stores the maximum length of an arithmetic subsequence ending at nums[i] with common difference j - 500

The algorithm works by:

1. For each element nums[i], examining all previous elements nums[k] where k < i
2. Calculating the difference j = nums[i] - nums[k] + 500 (adding 500 to handle negative differences since array indices must be non-negative)
3. Updating f[i][j] to be the maximum of its current value or f[k][j] + 1 (extending the arithmetic sequence ending at nums[k])
4. Tracking the maximum length found across all subsequences

The range of 1001 for the second dimension accounts for differences ranging from -500 to 500, shifted to [0, 1000] for array indexing purposes.

Intuition

The key insight is that an arithmetic subsequence is uniquely defined by two properties: its ending element and its common difference. If we know these two pieces of information, we can determine the entire subsequence by working backwards.

Think about building arithmetic subsequences incrementally. When we're at position i in the array, we want to know: what's the longest arithmetic subsequence that ends at nums[i]? But this question is incomplete - we also need to specify the common difference, because nums[i] could be the end of multiple arithmetic subsequences with different common differences.

For example, if nums = [1, 3, 5, 7] and we're at element 7, it could be:

• Part of subsequence [1, 7] with difference 6
• Part of subsequence [3, 5, 7] with difference 2
• Part of subsequence [5, 7] with difference 2

This naturally leads to a dynamic programming approach where our state is (ending position, common difference). For each element nums[i], we consider pairing it with every previous element nums[k] to form a potential arithmetic sequence. The difference nums[i] - nums[k] becomes our common difference.

The beautiful part is that if nums[k] was already part of an arithmetic subsequence with the same common difference, we can simply extend that subsequence by adding nums[i]. This is why f[i][j] = f[k][j] + 1 - we're taking the longest arithmetic subsequence ending at nums[k] with difference j and extending it by one element.

The offset of 500 is a technical detail to handle negative differences. Since array indices must be non-negative, and differences can range from -500 to 500 (based on typical constraints), we shift everything by 500 to map the range to [0, 1000].

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with a 2D table. The approach follows these steps:

1. Initialize the DP Table

Create a 2D array f where f[i][j] represents the maximum length of an arithmetic subsequence ending at index i with common difference j - 500. Initialize all values to 1 since each element by itself forms an arithmetic subsequence of length 1.

f = [[1] * 1001 for _ in range(n)]

The size 1001 accounts for all possible differences in the range [-500, 500] shifted to [0, 1000].

2. Fill the DP Table

For each position i from 1 to n-1:

• Consider all previous positions k from 0 to i-1
• Calculate the common difference: j = nums[i] - nums[k] + 500
• Update the DP value: f[i][j] = max(f[i][j], f[k][j] + 1)

This means we're either:

• Starting a new arithmetic subsequence of length 2 (since f[i][j] was initialized to 1)
• Extending an existing arithmetic subsequence that ended at position k with the same common difference

for i in range(1, n):
    for k in range(i):
        j = nums[i] - nums[k] + 500
        f[i][j] = max(f[i][j], f[k][j] + 1)
        ans = max(ans, f[i][j])

3. Track the Maximum Length

Throughout the process, we maintain ans as the maximum length found so far. We update it whenever we compute a new f[i][j] value.

Time and Space Complexity

• Time Complexity: O(n² × d) where n is the length of the array and d is the range of differences. Since d is constant (1001), this simplifies to O(n²).
• Space Complexity: O(n × d) which is O(n) since d is constant.

The algorithm efficiently finds the longest arithmetic subsequence by building up solutions for smaller subsequences and using them to construct longer ones, avoiding redundant calculations through memoization.

Example Walkthrough

Let's walk through the algorithm with nums = [3, 6, 9, 12].

Step 1: Initialize

• Create DP table f with dimensions 4×1001 (4 elements, 1001 possible differences)
• Initialize all values to 1
• Set ans = 1

Step 2: Process each element

When i = 1 (nums[1] = 6):

• Consider k = 0 (nums[0] = 3):
  • Difference = 6 - 3 = 3, so j = 3 + 500 = 503
  • f[1][503] = max(1, f[0][503] + 1) = max(1, 1 + 1) = 2
  • Update ans = 2

When i = 2 (nums[2] = 9):

• Consider k = 0 (nums[0] = 3):
  • Difference = 9 - 3 = 6, so j = 506
  • f[2][506] = max(1, f[0][506] + 1) = 2
  • ans remains 2
• Consider k = 1 (nums[1] = 6):
  • Difference = 9 - 6 = 3, so j = 503
  • f[2][503] = max(1, f[1][503] + 1) = max(1, 2 + 1) = 3
  • Update ans = 3

When i = 3 (nums[3] = 12):

• Consider k = 0 (nums[0] = 3):
  • Difference = 12 - 3 = 9, so j = 509
  • f[3][509] = 2
  • ans remains 3
• Consider k = 1 (nums[1] = 6):
  • Difference = 12 - 6 = 6, so j = 506
  • f[3][506] = max(1, f[1][506] + 1) = 2
  • ans remains 3
• Consider k = 2 (nums[2] = 9):
  • Difference = 12 - 9 = 3, so j = 503
  • f[3][503] = max(1, f[2][503] + 1) = max(1, 3 + 1) = 4
  • Update ans = 4

Result: The longest arithmetic subsequence is [3, 6, 9, 12] with length 4.

The key insight is how f[2][503] = 3 represents the subsequence [3, 6, 9] with difference 3, which we then extend to include 12, giving us f[3][503] = 4 for the complete sequence [3, 6, 9, 12].

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the length of the array nums.

The space complexity is O(n × d), where n is the length of the array nums and d is the range of possible differences.

Analysis:

For time complexity:

• The outer loop runs n-1 times (from index 1 to n-1)
• The inner loop runs up to i times for each iteration of the outer loop
• This gives us a total of 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 iterations
• Therefore, the time complexity is O(n²)

For space complexity:

• We create a 2D array f with dimensions n × 1001
• The value 1001 represents the range of possible differences after shifting by 500 (to handle negative differences)
• Since the array stores differences in the range [-500, 500], which is shifted to [0, 1000], we need 1001 positions
• This range d = 1001 is constant in this implementation but conceptually represents the difference between maximum and minimum possible values
• Therefore, the space complexity is O(n × 1001) = O(n × d)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Negative Differences

Pitfall: A common mistake is forgetting to offset the difference when using it as an array index. Since Python (and most languages) don't allow negative array indices for standard arrays, directly using nums[i] - nums[prev_idx] as an index will cause an error when the difference is negative.

Incorrect Code:

diff = nums[i] - nums[prev_idx]  # Could be negative!
dp[i][diff] = max(dp[i][diff], dp[prev_idx][diff] + 1)  # IndexError!

Solution: Always add an offset (typically 500 based on constraints) to ensure all differences map to valid non-negative indices:

diff_with_offset = nums[i] - nums[prev_idx] + 500
dp[i][diff_with_offset] = max(dp[i][diff_with_offset], dp[prev_idx][diff_with_offset] + 1)

2. Insufficient Array Size for DP Table

Pitfall: Using an incorrect size for the second dimension of the DP table. If the problem constraints indicate values can range from -500 to 500, the difference between any two elements can range from -1000 to 1000.

Incorrect Code:

dp = [[1] * 1001 for _ in range(n)]  # May not cover all possible differences!

Solution: Calculate the actual range based on problem constraints. If elements range from -500 to 500, differences range from -1000 to 1000, requiring an array size of 2001:

# If nums[i] can be [-500, 500], differences can be [-1000, 1000]
dp = [[1] * 2001 for _ in range(n)]
diff_with_offset = nums[i] - nums[prev_idx] + 1000  # Offset by 1000

3. Forgetting to Initialize Base Cases

Pitfall: Not initializing the DP table properly. Each element by itself forms an arithmetic subsequence of length 1, but forgetting this initialization leads to incorrect results.

Incorrect Code:

dp = [[0] * 1001 for _ in range(n)]  # Wrong! Should be 1, not 0

Solution: Initialize all values to 1 since every single element is an arithmetic subsequence of length 1:

dp = [[1] * 1001 for _ in range(n)]

4. Not Tracking the Maximum Properly

Pitfall: Only checking the maximum at the last position or forgetting to update it during the iteration.

Incorrect Code:

for i in range(1, n):
    for prev_idx in range(i):
        diff_with_offset = nums[i] - nums[prev_idx] + 500
        dp[i][diff_with_offset] = max(dp[i][diff_with_offset], 
                                      dp[prev_idx][diff_with_offset] + 1)
return max(max(row) for row in dp)  # Inefficient and unnecessary

Solution: Track the maximum length as you compute it:

max_length = 0
for i in range(1, n):
    for prev_idx in range(i):
        diff_with_offset = nums[i] - nums[prev_idx] + 500
        dp[i][diff_with_offset] = max(dp[i][diff_with_offset], 
                                      dp[prev_idx][diff_with_offset] + 1)
        max_length = max(max_length, dp[i][diff_with_offset])
return max_length

5. Memory Optimization Oversight

Pitfall: For very large inputs, the 2D DP table might consume excessive memory. Using a full 2D array when a dictionary-based approach could be more memory-efficient.

Memory-Optimized Solution:

def longestArithSeqLength(self, nums: List[int]) -> int:
    n = len(nums)
    dp = [{} for _ in range(n)]  # Use dictionaries instead of arrays
    max_length = 0
  
    for i in range(1, n):
        for prev_idx in range(i):
            diff = nums[i] - nums[prev_idx]
            # No offset needed with dictionaries
            dp[i][diff] = dp[prev_idx].get(diff, 1) + 1
            max_length = max(max_length, dp[i][diff])
  
    return max_length

This approach only stores the differences that actually occur, potentially saving significant memory when the range of differences is large but sparse.