Longest Arithmetic Subsequence of Given Difference: Hash Map DP

Given an integer array arr and an integer difference, find the length of the longest subsequence in arr such that the difference between adjacent elements is equal to difference. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

This is LeetCode 1218: Longest Arithmetic Subsequence of Given Difference. For example, given arr = [1, 5, 7, 8, 5, 3, 4, 2, 1] and difference = -2, the answer is 4 because the subsequence [7, 5, 3, 1] has adjacent differences of -2 and is the longest such subsequence.

Why this problem matters

This problem teaches one of the most useful DP patterns you will encounter: using a hash map as your DP table instead of an array. In many subsequence problems, the state space is too sparse or the values too large for a traditional DP array. A hash map gives you O(1) lookups and updates without wasting memory on unused indices.

Once you internalize this pattern, you will recognize it in a whole family of problems. Any time you need to track "the best answer ending at value x," a hash map is often the right tool. It comes up in longest increasing subsequence variants, chain-building problems, and any scenario where the DP key is a value rather than a position.

The key insight

The brute force approach would check every possible subsequence, which takes exponential time. But there is a much cleaner way to think about it.

For each element x in the array, ask: "Is there an element x - difference that I have already seen?" If so, I can extend whatever subsequence ended at x - difference by one more step. If not, x starts a fresh subsequence of length 1.

This gives you the recurrence: dp[x] = dp[x - difference] + 1 if x - difference exists in the map, otherwise dp[x] = 1. You process the array left to right in a single pass, and each element takes O(1) time to handle. The hash map stores the length of the longest valid subsequence ending at each value you have seen so far.

The beauty here is that you do not need to know where in the array the predecessor was. You only care about its value and the best subsequence length ending there. The hash map captures exactly that information and nothing more.

The solution

def longest_subsequence(arr, difference):
    dp = {}
    best = 0

    for x in arr:
        prev = x - difference
        dp[x] = dp.get(prev, 0) + 1
        best = max(best, dp[x])

    return best

1. Create an empty hash map dp where dp[x] will store the length of the longest valid subsequence ending with value x.
2. For each element x in the array, compute the predecessor value prev = x - difference.
3. Look up dp[prev]. If it exists, we can extend that subsequence. If not, dp.get(prev, 0) returns 0.
4. Set dp[x] = dp[prev] + 1, recording the new best length ending at x.
5. Track the global maximum across all entries.

Visual walkthrough

Notice how the map grows as we process each element. When we reach the second occurrence of 5 at index 4, we find dp[7] = 1 and set dp[5] = 2. When we reach 3, we find dp[5] = 2 and set dp[3] = 3. When we finally reach the second occurrence of 1 at index 8, we find dp[3] = 3 and set dp[1] = 4. Each step builds on what came before, and the map handles duplicate values naturally by overwriting with the better answer.

Complexity analysis

Time: O(n). We iterate through the array once. Each element involves a single hash map lookup and a single hash map insertion, both O(1) on average.

Space: O(n). The hash map stores at most one entry per distinct value in the array. In the worst case, all values are distinct, so the map holds n entries.

Edge cases

• All elements are the same with difference = 0: every element extends the previous one. For arr = [3, 3, 3, 3] and difference = 0, the answer is 4.
• No valid subsequence longer than 1: when no two elements differ by difference, every element forms its own length-1 subsequence. Return 1.
• Negative difference: the algorithm handles this naturally. If difference = -2 and x = 5, we look for dp[7], which is correct.
• Single element array: return 1. The element itself is a valid subsequence.
• Large positive and negative values: since we use a hash map instead of an array, we do not need to worry about the range of values. Keys can be anything.
• Duplicate values: later occurrences overwrite earlier ones in the map, which is correct because a later occurrence can always form an equally long or longer subsequence.

The building blocks

1. Hash map as DP table

The traditional DP approach uses an array indexed by position or by value. When the value space is large or sparse, a hash map is the better choice. You get the same O(1) lookup and update, but you only store entries for values you have actually seen. This pattern appears in problems like Longest Consecutive Sequence and Two Sum, where the hash map lets you find related elements without scanning the whole array.

2. Single-pass subsequence building

Instead of comparing every pair of elements (O(n^2)), you process the array once from left to right. At each element, you look up exactly one predecessor in the map and update exactly one entry. This "look back by value, not by index" technique works whenever the relationship between consecutive subsequence elements is determined by a fixed rule, like a constant difference or a constant ratio.

From understanding to recall

You can follow this walkthrough and see exactly why each map update happens. But could you write this solution from scratch in a week? The gap between understanding a hash map DP solution and producing one under pressure is real. The recurrence dp[x] = dp[x - difference] + 1 is simple, but remembering to use a hash map instead of an array, knowing which predecessor to look up, and handling the edge cases all need to become automatic.

Spaced repetition is how you close that gap. You revisit the problem at increasing intervals, write the solution from memory each time, and after a few reps the hash map DP pattern becomes second nature. This pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually beats random problem grinding every time.

Related posts

• Longest Arithmetic Subsequence - The more general version where you find the longest arithmetic subsequence with any common difference
• Longest Increasing Subsequence - Classic DP subsequence problem that teaches the foundation for all subsequence DP
• Coin Change - Another DP problem where you look up a computed predecessor value, but uses an array instead of a hash map