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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestArithSeqLength(int[] nums) {
6 if (nums.Length <= 2) return nums.Length;
7 var dp = new Dictionary<int, int>[nums.Length];
8 int maxLength = 2;
9 for (int i = 0; i < nums.Length; i++) {
10 dp[i] = new Dictionary<int, int>();
11 for (int j = 0; j < i; j++) {
12 int diff = nums[i] - nums[j];
13 if (dp[j].ContainsKey(diff)) {
dp[i][diff] = dp[j][diff] + 1;
} else {
dp[i][diff] = 2;
}
maxLength = Math.Max(maxLength, dp[i][diff]);
}
}
return maxLength;
}
public static void Main(string[] args) {
int[] nums = {3, 6, 9, 12};
var sol = new Solution();
Console.WriteLine(sol.LongestArithSeqLength(nums));
}
}The C# version employs an array of dictionaries to map the length of arithmetic sequences by their differences. By iterating over all pairs of indices and computing differences, it checks and updates `dp[i]` to reflect the new lengths of the 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.
1using System.Collections.Generic;
public class Solution {
public int LongestArithSeqLength(int[] nums) {
if (nums.Length <= 2) return nums.Length;
var dp = new Dictionary<int, int>[nums.Length];
int maxLength = 2;
for (int i = 0; i < nums.Length; i++) {
dp[i] = new Dictionary<int, int>();
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
if (dp[j].ContainsKey(diff)) {
dp[i][diff] = dp[j][diff] + 1;
} else {
dp[i][diff] = 2;
}
maxLength = Math.Max(maxLength, dp[i][diff]);
}
}
return maxLength;
}
public static void Main() {
int[] nums = {9, 4, 7, 2, 10};
var sol = new Solution();
Console.WriteLine(sol.LongestArithSeqLength(nums));
}
}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 C# code handles the longest arithmetic subsequence problem by establishing dictionaries for each element in the array, keeping score of different arithmetic sequences iteratively and effectively.