Longest Arithmetic Subsequence
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible starting pair of elements in the array to form an arithmetic subsequence. For each pair, it determines the common difference and then scans the rest of the array to find subsequent elements that fit the sequence.
Algorithm
- Initialize
maxLengthto 2, as any pair of numbers forms an arithmetic sequence of length 2. - Use a nested loop to pick every pair of elements
(nums[i], nums[j])withi < j. - For each pair, calculate the common difference
d = nums[j] - nums[i]. - Start a sequence with these two elements, so
currentLength = 2andlastElement = nums[j]. - Iterate through the rest of the array from index
j + 1. - If an element
nums[k]is found such thatnums[k] == lastElement + d, incrementcurrentLengthand updatelastElementtonums[k]. - After checking all elements for the current pair, update
maxLength = max(maxLength, currentLength). - Return
maxLength.
Walkthrough
The core idea is to fix the first two elements of a potential arithmetic subsequence, which in turn defines the common difference. We iterate through all possible pairs of indices (i, j) where i < j. For each pair, nums[i] and nums[j] start a sequence of length 2. The difference is d = nums[j] - nums[i]. We then iterate from k = j + 1 to the end of the array, looking for the next term, which should be nums[j] + d. If we find it, we extend the sequence and look for the subsequent term. We keep track of the maximum length found across all starting pairs.
class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length; if (n <= 2) { return n; } int maxLength = 2; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int diff = nums[j] - nums[i]; int currentLength = 2; int lastElement = nums[j]; for (int k = j + 1; k < n; k++) { if (nums[k] == lastElement + diff) { currentLength++; lastElement = nums[k]; } } maxLength = Math.max(maxLength, currentLength); } } return maxLength; }}Complexity
Time
O(n^3), where n is the number of elements in `nums`. There are three nested loops, each potentially iterating up to n times.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
This approach uses dynamic programming to build up solutions for longer arithmetic subsequences from shorter ones. We maintain a DP table where dp[i] stores information about all arithmetic subsequences ending at index i.
Algorithm
- Initialize
maxLength = 2. - Create an array of HashMaps,
dp, of sizen.dp[i]will store{difference: length}pairs for subsequences ending atnums[i]. - Iterate
ifrom 0 ton-1:- Initialize
dp[i] = new HashMap<>(). - Iterate
jfrom 0 toi-1:- Calculate
diff = nums[i] - nums[j]. - Get the length of the sequence ending at
jwith thisdiff.length = dp[j].getOrDefault(diff, 1). - The new length ending at
iislength + 1. - Update
dp[i].put(diff, length + 1). - Update
maxLength = max(maxLength, length + 1).
- Calculate
- Initialize
- Return
maxLength.
Walkthrough
The state dp[i] will be a hash map where dp[i][d] stores the length of the arithmetic subsequence ending at index i with a common difference d. We iterate through the array with an outer loop for i from 0 to n-1. For each i, we have an inner loop for j from 0 to i-1. Inside the inner loop, we calculate the difference d = nums[i] - nums[j]. The pair (nums[j], nums[i]) can extend any arithmetic subsequence ending at j with the same difference d. The length of the new subsequence ending at i is dp[j][d] + 1. If no such subsequence exists ending at j, (nums[j], nums[i]) forms a new subsequence of length 2. We can model this by dp[i].put(d, dp[j].getOrDefault(d, 1) + 1). The default value of 1 represents the subsequence containing only nums[j]. We keep track of the maximum length found during this process.
import java.util.HashMap;import java.util.Map; class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length; int maxLength = 2; Map<Integer, Integer>[] dp = new HashMap[n]; for (int i = 0; i < n; i++) { dp[i] = new HashMap<>(); for (int j = 0; j < i; j++) { int diff = nums[i] - nums[j]; int newLength = dp[j].getOrDefault(diff, 1) + 1; dp[i].put(diff, newLength); maxLength = Math.max(maxLength, newLength); } } return maxLength; }}Complexity
Time
O(n^2), where n is the number of elements. This is due to the two nested loops. HashMap operations take average O(1) time.
Space
O(n^2). In the worst case, `dp[i]` can have `i` distinct differences. The total number of entries across all maps is `1 + 2 + ... + (n-1)`, which is `O(n^2)`.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.
Cons
Requires O(n^2) space, which can be large for n=1000.
This approach optimizes the DP solution by changing the iteration strategy. Instead of iterating through pairs of indices, we iterate through all possible common differences d. For each fixed d, we find the length of the longest arithmetic subsequence with that difference in O(n) time.
Algorithm
- Determine the range of possible differences. Given
0 <= nums[i] <= 500, the differencedis in[-500, 500]. - Initialize
maxLength = 2. - Iterate
dfrom -500 to 500:- Initialize a HashMap
dpfor the current difference.dpmaps a value to the length of the AP ending with that value. - Iterate through each
numin thenumsarray:- The previous value in the sequence would be
prev = num - d. - The length of the AP ending at
numisdp.getOrDefault(prev, 0) + 1. - Update
dp.put(num, ...)with this new length. - Update
maxLength = max(maxLength, dp.get(num)).
- The previous value in the sequence would be
- Initialize a HashMap
- Return
maxLength.
Walkthrough
Given that the values in nums are constrained to [0, 500], the common difference d must be in the range [-500, 500]. We can iterate through every possible difference d in this range. For a fixed d, the problem reduces to finding the longest subsequence a_1, a_2, ..., a_k where a_{i+1} = a_i + d. This can be solved in a single pass through the nums array using a hash map. Let dp[value] be the length of the arithmetic subsequence with difference d ending with value. When we process an element num from nums, the previous element in the sequence would have been num - d. The length of the new sequence ending at num is dp.getOrDefault(num - d, 0) + 1. We update dp[num] with this new length and track the overall maximum length.
import java.util.HashMap;import java.util.Map; class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length; int maxLength = 2; for (int diff = -500; diff <= 500; diff++) { Map<Integer, Integer> dp = new HashMap<>(); for (int num : nums) { int prev = num - diff; int prevLength = dp.getOrDefault(prev, 0); int currentLength = prevLength + 1; dp.put(num, currentLength); maxLength = Math.max(maxLength, currentLength); } } return maxLength; }}Complexity
Time
O(N * D), where N is the length of `nums` and D is the range of values in `nums`. Here, D is `max(nums) - min(nums)`. The number of differences is `2*D+1`. For the given constraints, this is approximately `1000 * 1001`, which is faster than `O(N^2)`.
Space
O(N). For each difference `d`, we use a hash map that can store up to `N` elements. This map is reset for each new difference, so the space is not cumulative.
Trade-offs
Pros
Most efficient approach for the given constraints.
Better time complexity than the standard O(N^2) DP when the range of values is smaller than N.
Cons
Performance is dependent on the range of values in the input array. If values were unbounded, this would be inefficient.
Solutions
Solution
class Solution {public int longestArithSeqLength(int[] nums) { int n = nums.length; int ans = 0; int[][] f = new int[n][1001]; for (int i = 1; i < n; ++i) { for (int k = 0; k < i; ++k) { int j = nums[i] - nums[k] + 500; f[i][j] = Math.max(f[i][j], f[k][j] + 1); ans = Math.max(ans, f[i][j]); } } return ans + 1; }}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 ansclass Solution {public: int longestArithSeqLength(vector<int> &nums) { int n = nums.size(); int f[n][1001]; memset(f, 0, sizeof(f)); int ans = 0; for (int i = 1; i < n; ++i) { for (int k = 0; k < i; ++k) { int 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 + 1; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.