The Longest Arithmetic Subsequence interview question gives you an array of integers and asks you to find the length of the longest subsequence where the difference between any two consecutive elements is constant. A subsequence means you can delete some elements from the original array without changing the order of the remaining elements. For example, in [3, 6, 9, 12], the difference is consistently 3.
Interviewers love this array problem because it flawlessly blends two core concepts: combinations and optimization. It tests your ability to recognize that finding all possible subsequences via brute force is impossibly slow (exponential time), pushing you to find a more elegant solution. It is highly effective at assessing a candidate's grasp of advanced data structures and their ability to keep track of multiple states simultaneously.
This problem is a quintessential application of Dynamic Programming combined with a Hash Table. You create an array of hash maps (or a 2D array if the constraints are small), where dp[i][diff] represents the length of the longest arithmetic subsequence ending at index i with a specific difference diff. By iterating through all pairs of elements, you calculate their difference and update the state based on previously computed subsequences.
Let's look at the array: [9, 4, 7, 2, 10].
We check pairs (i, j) where i < j:
i=0 (9), j=1 (4): Difference is -5. dp[1][-5] = dp[0][-5] + 1 = 2. Length is 2.i=1 (4), j=2 (7): Difference is 3. dp[2][3] = dp[1][3] + 1 = 2.i=1 (4), j=4 (10): Difference is 6. dp[4][6] = dp[1][6] + 1 = 2.
Let's look at a simpler sequence: [2, 4, 6, 8].
Difference between 4 and 2 is 2. Length ending at 4 with diff 2 is 2.
Difference between 6 and 4 is 2. Length ending at 6 with diff 2 becomes (length at 4 with diff 2) + 1 = 3.
Difference between 8 and 6 is 2. Length becomes 3 + 1 = 4.
The longest subsequence is dynamically built as we traverse.A major pitfall is trying to sort the array. Remember, this is about subsequences, so the original order of elements matters; sorting destroys this order. Another mistake is using a simple 1D DP array. Unlike the Longest Increasing Subsequence problem, here you must track BOTH the ending index and the specific difference, which is why a 2D approach (or array of dictionaries) is strictly required.
When studying the Longest Arithmetic Subsequence coding pattern, ensure you are very comfortable with arrays of hash maps. Because the "difference" can be negative or positive, using a hash map for the second dimension of your DP table avoids negative index out-of-bounds errors and handles sparse differences perfectly.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Longest Square Streak in an Array | Medium | Solve | |
| Maximum Earnings From Taxi | Medium | Solve | |
| Find Two Non-overlapping Sub-arrays Each With Target Sum | Medium | Solve | |
| Maximize the Profit as the Salesman | Medium | Solve | |
| Length of Longest Fibonacci Subsequence | Medium | Solve |