Watch 10 video solutions for Longest Arithmetic Subsequence of Given Difference, a medium level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by codestorywithMIK has 6,268 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.
A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
1 <= arr.length <= 105-104 <= arr[i], difference <= 104Problem Overview: You receive an integer array arr and a fixed integer difference. The goal is to find the length of the longest subsequence where the difference between consecutive elements is exactly difference. The subsequence does not need to be contiguous, but the order of elements must remain the same.
Approach 1: Dynamic Programming with HashMap (Time: O(n), Space: O(n))
The key observation: if a number x appears in the array, the previous value in a valid arithmetic subsequence must be x - difference. Maintain a hash map where dp[x] stores the length of the longest subsequence ending with value x. Iterate through the array once. For each value x, check if x - difference already exists in the map. If it does, extend that subsequence: dp[x] = dp[x - difference] + 1. Otherwise start a new subsequence with length 1. Update the map and track the maximum length. Hash lookups keep the operation constant time, giving a linear pass solution. This approach relies heavily on Hash Table lookups combined with Dynamic Programming state transitions.
Approach 2: Optimized Dynamic Programming with Direct Indexing (Time: O(n), Space: O(n))
If the value range of the array is reasonably bounded, the hash map can be replaced with a direct-index array. Instead of storing states in a map, use an array where the index represents the number itself (with offset if negatives exist). For each element x, compute x - difference and look up the stored subsequence length directly from the DP array. Then update the current index with the extended length. Direct indexing removes hash overhead and improves constant factors while keeping the same recurrence. This technique still follows the same Array-based dynamic programming idea but trades memory for faster access.
Recommended for interviews: The hash map dynamic programming solution is the expected answer. It demonstrates that you recognized the recurrence relationship between values and used a constant-time lookup structure. Mentioning the direct-index optimization shows deeper understanding of performance tradeoffs. Interviewers usually care most about identifying the DP state dp[x] and deriving the transition dp[x] = dp[x - difference] + 1.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with HashMap | O(n) | O(n) | General case. Works for any integer range and is the most common interview solution. |
| Optimized DP with Direct Indexing | O(n) | O(n) | When value range is limited and you want faster constant-time lookups without hash overhead. |