Watch 10 video solutions for Longest Arithmetic Subsequence, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by codestorywithMIK has 10,998 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 500Problem Overview: Given an integer array nums, find the length of the longest subsequence where the difference between consecutive elements is constant. The subsequence does not need to be contiguous, but the order must remain the same.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct strategy tries every pair of indices as the first two elements of a potential arithmetic subsequence. Once the difference diff = nums[j] - nums[i] is fixed, scan the rest of the array and greedily extend the sequence whenever the next expected value appears. This approach repeatedly searches the array for the next valid element, which leads to a cubic runtime in the worst case. It demonstrates the core idea—fix a difference and extend the sequence—but becomes impractical for large inputs.
Approach 2: Dynamic Programming with 2D DP Array (O(n^2) time, O(n^2) space)
A better solution stores results for subproblems. Define dp[i][d] as the length of the longest arithmetic subsequence ending at index i with difference d. For every pair of indices j < i, compute diff = nums[i] - nums[j]. If a sequence ending at j with this difference already exists, extend it: dp[i][diff] = dp[j][diff] + 1. Otherwise start a new sequence of length 2. This dynamic programming transition builds longer subsequences as you iterate through the array. The method fits naturally into dynamic programming patterns but can consume significant memory if differences are stored in a dense structure.
Approach 3: Dynamic Programming with HashMap Optimization (O(n^2) time, O(n^2) space)
The most practical implementation replaces the dense DP table with a hash map for each index. Each dp[i] is a map where the key is the difference and the value is the subsequence length ending at i. For every pair (j, i), compute the difference and perform a constant‑time hash lookup: dp[i][diff] = dp[j].get(diff, 1) + 1. This avoids allocating a large fixed difference range and stores only the differences that actually appear. The algorithm still checks every pair of indices, giving O(n^2) time, but the memory usage becomes much more practical. This technique combines ideas from array iteration and hash table lookups.
Recommended for interviews: Interviewers expect the dynamic programming insight. Starting with the brute force explanation shows you understand the arithmetic subsequence definition, but the HashMap DP solution demonstrates algorithmic maturity. It keeps the optimal O(n^2) time while handling arbitrary differences efficiently, which is the approach most candidates implement during interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Conceptual baseline to understand how arithmetic subsequences are formed |
| Dynamic Programming with 2D DP Array | O(n^2) | O(n^2) | When implementing a straightforward DP table and difference range is manageable |
| Dynamic Programming with HashMap Optimization | O(n^2) | O(n^2) | Preferred solution for interviews and real implementations with large difference ranges |