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.
1def longestArithSeqLength(nums):
2 if len(nums) <= 2:
3 return len(nums)
4 dp = [{}
The Python implementation utilizes a list of dictionaries to manage the lengths of arithmetic subsequences for each index and their respective differences. For every element `nums[i]`, it examines all preceding elements `nums[j]`, calculates the difference, and attempts to extend existing sequences.
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.
JavaScript provides a succinct implementation of the solution using built-in Maps, iterating through pairs of indices and managing difference-based sequence length efficiently in terms of both computation and space.