To solve the Longest Arithmetic Subsequence problem, start by tracking differences between elements and storing subsequence lengths in a hash map. Iterate over the array, updating the map to extend sequences with consistent differences. This approach ensures all pairs are considered without redundant recalculations, balancing speed and memory use while maintaining clarity on subsequence growth.
Problem Statement
Given an integer array nums, return the length of the longest subsequence where the difference between consecutive elements is constant. Each element may be part of multiple subsequences, and the subsequence does not need to be contiguous in the array.
For example, in nums = [3,6,9,12], the entire array forms an arithmetic sequence with a step of 3, resulting in length 4. In nums = [9,4,7,2,10], the longest arithmetic subsequence is [4,7,10] with length 3. Constraints: 2 <= nums.length <= 1000, 0 <= nums[i] <= 500.
Examples
Example 1
Input: nums = [3,6,9,12]
Output: 4
The whole array is an arithmetic sequence with steps of length = 3.
Example 2
Input: nums = [9,4,7,2,10]
Output: 3
The longest arithmetic subsequence is [4,7,10].
Example 3
Input: nums = [20,1,15,3,10,5,8]
Output: 4
The longest arithmetic subsequence is [20,15,10,5].
Constraints
- 2 <= nums.length <= 1000
- 0 <= nums[i] <= 500
Solution Approach
Hash Map DP Approach
Use a dynamic programming table where each element keeps a hash map of differences to subsequence lengths. Iterate through the array and for each nums[i], check all previous nums[j] to update the difference count. Update the global maximum whenever a longer subsequence is found.
Iterative Pair Scanning
Scan all pairs of elements to calculate the difference and store the length of the subsequence ending at the current element with that difference. This avoids recomputation and directly extends existing arithmetic subsequences using hash lookup for differences.
Optimizing Space
Instead of a 2D array, store a list of hash maps for each index. Each map tracks differences to subsequence lengths. This reduces space usage from O(n^2) to O(n*d) where d is the number of unique differences encountered, while maintaining fast access for updates.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n^2) due to scanning all pairs of elements, and space complexity is O(n*d) because each element maintains a hash map of differences to subsequence lengths, where d is the number of unique differences in the array.
What Interviewers Usually Probe
- Asks about hash map usage for tracking differences
- Tests understanding of DP and subsequence extension
- Probes for handling large arrays within constraints
Common Pitfalls or Variants
Common pitfalls
- Not updating the hash map correctly for each difference
- Assuming subsequences must be contiguous
- Overlooking large differences or negative steps in subsequences
Follow-up variants
- Find the longest arithmetic subsequence with a fixed common difference
- Return the actual longest arithmetic subsequence, not just length
- Handle sequences where elements can repeat
How GhostInterview Helps
- Provides step-by-step explanation of hash map DP for differences
- Highlights correct iteration and pair scanning strategy
- Offers example walkthroughs for common patterns and failure cases
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the Longest Arithmetic Subsequence problem about?
It asks for the length of the longest subsequence in an array where consecutive elements have the same difference.
How does the array scanning plus hash lookup pattern apply here?
It lets you track subsequence lengths by difference efficiently, updating counts without recomputing existing sequences.
Can the subsequence be non-contiguous?
Yes, elements do not need to be next to each other as long as the arithmetic difference is consistent.
What is the time complexity of the standard solution?
The approach that scans all pairs and uses hash maps has O(n^2) time complexity.
How do negative or large differences affect the solution?
All differences, including negative or large ones, are stored in the hash map for each element, ensuring correctness regardless of step size.
Need direct help with Longest Arithmetic Subsequence instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Arithmetic Subsequence from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given a string s and a list of words, count how many words are subsequences of s using efficient array scanning and hash lookup.
Open problem page#1477 Find Two Non-overlapping Sub-arrays Each With Target SumFind two non-overlapping sub-arrays with a given target sum and return the minimal total length efficiently using array scanning and hash lookup.
Open problem page#2008 Maximum Earnings From TaxiMaximize earnings by optimizing taxi ride selection and tips using array scanning, hash lookups, and sorting.
Open problem page