Longest Arithmetic Subsequence - Solution & Explanation
Problem Statement
Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.
Note that:
- A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
- A sequence
seqis arithmetic ifseq[i + 1] - seq[i]are all the same value (for0 <= i < seq.length - 1).
Example 1:
Input: nums = [3,6,9,12] Output: 4 Explanation: The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: nums = [9,4,7,2,10] Output: 3 Explanation: The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: nums = [20,1,15,3,10,5,8] Output: 4 Explanation: The longest arithmetic subsequence is [20,15,10,5].
Constraints:
2 <= nums.length <= 10000 <= nums[i] <= 500
Approach Overview
Problem Overview: Given an integer array nums, find the length of the longest subsequence where the difference between consecutive elements is constant. The subsequence does not need to be contiguous, but the order must remain the same.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct strategy tries every pair of indices as the first two elements of a potential arithmetic subsequence. Once the difference diff = nums[j] - nums[i] is fixed, scan the rest of the array and greedily extend the sequence whenever the next expected value appears. This approach repeatedly searches the array for the next valid element, which leads to a cubic runtime in the worst case. It demonstrates the core idea—fix a difference and extend the sequence—but becomes impractical for large inputs.
Approach 2: Dynamic Programming with 2D DP Array (O(n^2) time, O(n^2) space)
A better solution stores results for subproblems. Define dp[i][d] as the length of the longest arithmetic subsequence ending at index i with difference d. For every pair of indices j < i, compute diff = nums[i] - nums[j]. If a sequence ending at j with this difference already exists, extend it: dp[i][diff] = dp[j][diff] + 1. Otherwise start a new sequence of length 2. This dynamic programming transition builds longer subsequences as you iterate through the array. The method fits naturally into dynamic programming patterns but can consume significant memory if differences are stored in a dense structure.
Approach 3: Dynamic Programming with HashMap Optimization (O(n^2) time, O(n^2) space)
The most practical implementation replaces the dense DP table with a hash map for each index. Each dp[i] is a map where the key is the difference and the value is the subsequence length ending at i. For every pair (j, i), compute the difference and perform a constant‑time hash lookup: dp[i][diff] = dp[j].get(diff, 1) + 1. This avoids allocating a large fixed difference range and stores only the differences that actually appear. The algorithm still checks every pair of indices, giving O(n^2) time, but the memory usage becomes much more practical. This technique combines ideas from array iteration and hash table lookups.
Recommended for interviews: Interviewers expect the dynamic programming insight. Starting with the brute force explanation shows you understand the arithmetic subsequence definition, but the HashMap DP solution demonstrates algorithmic maturity. It keeps the optimal O(n^2) time while handling arbitrary differences efficiently, which is the approach most candidates implement during interviews.
Approach 1: Dynamic Programming with 2D DP Array
This approach involves using a 2D dynamic programming array to keep track of the lengths of arithmetic subsequences ending at different indices with various common differences. The outer loop iterates over end indices while the inner loop considers all pairs of start and end indices to update the subsequence lengths.
The C solution uses a 2D array `dp` where `dp[i][diff]` stores the longest arithmetic subsequence ending at `i` with common difference `diff`. Differences are adjusted by +500 to convert negative indices to positive. This approach scans each pair of indices `(j, i)` and computes the difference between elements. If a sequence with this difference already exists ending at `j`, it is extended by `i`.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(n^2), where n is the size of the input array.
Approach 2: Dynamic Programming with HashMap Optimization
This approach uses a simplified dynamic programming technique with HashMaps and tracks differences and their counts for each number. By leveraging HashMap structures, we manage subsequence lengths more efficiently and avoid using unnecessary space for non-existent differences.
This C implementation uses custom HashMap structures for each position to track possible differences and their lengths efficiently. It avoids using a full 2D array of fixed size by dynamically storing only necessary computations.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(n^2) in the worst case but often much less due to sparse differences.
Approach 3: 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.
Since the common difference may be negative, and the maximum difference is
500, we can uniformly add500to the common difference, so the range of the common difference becomes[0, 1000].
Considering f[i], we can enumerate the previous element nums[k] of nums[i], then the common difference j=nums[i]-nums[k]+500, at this time f[i][j]=max(f[i][j], f[k][j]+1), then we update the answer ans=max(ans, f[i][j]).
Finally, return the answer.
If initially
f[i][j]=0, then we need to add1to the answer when returning the answer.
The time complexity is O(n times (d + n)), and the space complexity is O(n times d). Where n and d are the length of the array nums and the difference between the maximum and minimum values in the array nums, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with 2D DP Array | Time Complexity: O(n^2) |
| Dynamic Programming with HashMap Optimization | Time Complexity: O(n^2) |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Conceptual baseline to understand how arithmetic subsequences are formed |
| Dynamic Programming with 2D DP Array | O(n^2) | O(n^2) | When implementing a straightforward DP table and difference range is manageable |
| Dynamic Programming with HashMap Optimization | O(n^2) | O(n^2) | Preferred solution for interviews and real implementations with large difference ranges |
Video Solution
Longest Arithmetic Subsequence | Recur + Memo | Bottom Up | GOOGLE | Leetcode-1027 | Live Code • codestorywithMIK • 12,258 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Arithmetic Subsequence easy or hard?
How to solve Longest Arithmetic Subsequence in O(n)?
Longest Arithmetic Subsequence Python or Java solution?
What is the best approach for Longest Arithmetic Subsequence?
What data structure is used in Longest Arithmetic Subsequence?
What is the time complexity of Longest Arithmetic Subsequence?
Is Longest Arithmetic Subsequence asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Longest Arithmetic Subsequence with our built-in code editor and test cases.
Practice on FleetCode