#1027

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Arithmetic Subsequence

Find the length of the longest arithmetic subsequence in a given integer array using scanning and hash-based lookup.

array hash table binary search dynamic programming

Problem Statement

Given an integer array nums, return the length of the longest subsequence where the difference between consecutive elements is constant. Each element may be part of multiple subsequences, and the subsequence does not need to be contiguous in the array.

For example, in nums = [3,6,9,12], the entire array forms an arithmetic sequence with a step of 3, resulting in length 4. In nums = [9,4,7,2,10], the longest arithmetic subsequence is [4,7,10] with length 3. Constraints: 2 <= nums.length <= 1000, 0 <= nums[i] <= 500.

Examples

Example 1

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

Output: 4

The whole array is an arithmetic sequence with steps of length = 3.

Example 2

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

Output: 3

The longest arithmetic subsequence is [4,7,10].

Example 3

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

Output: 4

The longest arithmetic subsequence is [20,15,10,5].

Constraints

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

Solution Approach

Hash Map DP Approach

Use a dynamic programming table where each element keeps a hash map of differences to subsequence lengths. Iterate through the array and for each nums[i], check all previous nums[j] to update the difference count. Update the global maximum whenever a longer subsequence is found.

Iterative Pair Scanning

Scan all pairs of elements to calculate the difference and store the length of the subsequence ending at the current element with that difference. This avoids recomputation and directly extends existing arithmetic subsequences using hash lookup for differences.

Optimizing Space

Instead of a 2D array, store a list of hash maps for each index. Each map tracks differences to subsequence lengths. This reduces space usage from O(n^2) to O(n*d) where d is the number of unique differences encountered, while maintaining fast access for updates.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to scanning all pairs of elements, and space complexity is O(n*d) because each element maintains a hash map of differences to subsequence lengths, where d is the number of unique differences in the array.

What Interviewers Usually Probe

Asks about hash map usage for tracking differences
Tests understanding of DP and subsequence extension
Probes for handling large arrays within constraints

Common Pitfalls or Variants

Common pitfalls

Not updating the hash map correctly for each difference
Assuming subsequences must be contiguous
Overlooking large differences or negative steps in subsequences

Follow-up variants

Find the longest arithmetic subsequence with a fixed common difference
Return the actual longest arithmetic subsequence, not just length
Handle sequences where elements can repeat

FAQ

What is the Longest Arithmetic Subsequence problem about?

It asks for the length of the longest subsequence in an array where consecutive elements have the same difference.

How does the array scanning plus hash lookup pattern apply here?

It lets you track subsequence lengths by difference efficiently, updating counts without recomputing existing sequences.

Can the subsequence be non-contiguous?

Yes, elements do not need to be next to each other as long as the arithmetic difference is consistent.

What is the time complexity of the standard solution?

The approach that scans all pairs and uses hash maps has O(n^2) time complexity.

How do negative or large differences affect the solution?

All differences, including negative or large ones, are stored in the hash map for each element, ensuring correctness regardless of step size.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the maximum length of the arithmetic sequence ending with $nums[i]$ and having a common difference of $j$. Initially, $f[i][j]=1$, that is, each element itself is an arithmetic sequence of length $1$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[1] * 1001 for _ in range(n)]
        ans = 0
        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])
        return ans

Continue Practicing

#792 number of matching subsequences #1477 find two non overlapping sub arrays each with target sum #2008 maximum earnings from taxi