Longest Arithmetic Subsequence of Given Difference

Longest Arithmetic Subsequence of Given Difference

What is this problem about?

The Longest Arithmetic Subsequence of Given Difference is an array problem where you are provided an integer array and a specific integer difference. Your task is to find the length of the longest subsequence within the array such that every adjacent pair of elements in the subsequence has exactly that given difference. It is a more constrained, yet often more efficiently solvable, variation of the general arithmetic subsequence problem.

Why is this asked in interviews?

This coding problem is a favorite in technical interviews because it has a beautifully elegant, linear-time solution. It acts as a litmus test to see if a candidate can spot when dynamic programming can be flattened down to a single dimension. Interviewers ask this to evaluate your problem-solving speed and your ability to optimize space and time complexities using straightforward data structures like hash maps.

Algorithmic pattern used

The optimal strategy relies on the Dynamic Programming and Hash Table pattern. Because the target difference is known ahead of time, you don't need to check all pairs of elements. Instead, you can iterate through the array just once. For each element num, you check if num - difference already exists in your hash map. If it does, you simply append your current number to that subsequence length.

Example explanation

Suppose the array is [1, 5, 7, 8, 5, 3, 4, 2, 1] and the difference = -2. We iterate through and keep a map of value -> max_length.

• See 1: Is 1 - (-2) = 3 in map? No. map[1] = 1.
• See 5: Is 7 in map? No. map[5] = 1.
• See 7: Is 9 in map? No. map[7] = 1.
• See 8: Is 10 in map? No. map[8] = 1.
• See 5 again: Is 7 in map? Yes (map[7] = 1). So map[5] = map[7] + 1 = 2.
• See 3: Is 5 in map? Yes (map[5] = 2). So map[3] = map[5] + 1 = 3.
• See 1 again: Is 3 in map? Yes (map[3] = 3). So map[1] = map[3] + 1 = 4. The longest sequence is [7, 5, 3, 1] with a length of 4.

Common mistakes candidates make

A typical error candidates make is applying the standard O(N^2) dynamic programming solution used for the generic arithmetic subsequence problem. Because the difference is a fixed constant, checking every previous index is unnecessary and leads to a Time Limit Exceeded error on large inputs. Another mistake is forgetting to initialize the length of a standalone element as 1.

Interview preparation tip

To master the Longest Arithmetic Subsequence of Given Difference interview question, focus on the power of "looking backwards" mathematically. Whenever an array problem asks you to build a chain based on a fixed numerical gap, immediately think of a hash map where you look up current_value - gap. This O(N) trick is a tremendous time-saver and shows deep algorithmic maturity.