Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.
Note that:
seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= 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] <= 500The key challenge in Longest Arithmetic Subsequence is tracking subsequences where the difference between consecutive elements remains constant. A common way to approach this is by using dynamic programming with hash maps.
For each index i, consider all previous indices j < i and compute the difference diff = nums[i] - nums[j]. Maintain a DP structure where each position stores a map of difference → length of subsequence. If a subsequence with the same difference already ends at j, extend it; otherwise start a new sequence of length 2. This efficiently builds longer arithmetic subsequences while iterating through the array.
This approach avoids checking all subsequences explicitly and instead incrementally builds solutions. The method typically runs in O(n²) time with O(n²) space in the worst case, which is suitable for interview constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Hash Map (difference tracking) | O(n^2) | O(n^2) |
NeetCode
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.
Time Complexity: O(n^2)
Space Complexity: O(n^2), where n is the size of the input array.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6int longestArithSeqLength(vector<int>& nums) {
7 if (nums.size() <= 2) return nums.size();
8 vector<unordered_map<int, int>> dp(nums.size());
9 int maxLength = 2;
10 for (int i = 0; i < nums.size(); i++) {
11 for (int j = 0; j < i; j++) {
12 int diff = nums[i] - nums[j];
13 dp[i][diff] = dp[j].count(diff) > 0 ? dp[j][diff] + 1 : 2;
maxLength = max(maxLength, dp[i][diff]);
}
}
return maxLength;
}
int main() {
vector<int> nums = {3, 6, 9, 12};
cout << longestArithSeqLength(nums) << endl;
return 0;
}This C++ solution uses a vector of hashmaps to store the length of arithmetic subsequences by their common differences. For each pair `(j, i)`, we calculate the difference and check if it already exists in `dp[j]`. If it does, we can extend this sequence to include `nums[i]`.
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.
Time Complexity: O(n^2)
Space Complexity: O(n^2) in the worst case but often much less due to sparse differences.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews at large tech companies. It tests understanding of dynamic programming, hash maps, and pairwise iteration patterns commonly used in sequence problems.
A hash map combined with dynamic programming works best. Each index stores a map where the key is the arithmetic difference and the value is the length of the longest subsequence ending at that index with that difference.
The optimal approach uses dynamic programming with a hash map to track subsequence lengths by their common difference. For every pair of indices, compute the difference and extend an existing subsequence if possible. This reduces the problem to O(n^2) time instead of exploring all subsequences.
Dynamic programming helps reuse previously computed subsequence lengths. By storing results for earlier indices and differences, we can extend subsequences efficiently rather than recomputing possibilities from scratch.
This Java implementation uses arrays of hashmaps to keep memory use low and operations fast by storing only active computations for each number at each step.