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.
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; }}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.