1218. Longest Arithmetic Subsequence of Given Difference

Problem¶

Given arr and difference, return the maximum length of a subsequence whose adjacent values always differ by difference.

arr = [1, 5, 7, 8, 5, 3, 4, 2, 1], difference = -2
subsequence = [7, 5, 3, 1]
output = 4

Key trick¶

Store the longest subsequence ending at each value. For each x, its predecessor must be exactly x - difference, so:

Trap¶

• Checking every existing subsequence makes the solution \(O(n^2)\).
• Greedily extending the first matching subsequence can miss a longer chain ending at the same value.
• Reversing arr to handle a negative difference is unnecessary and may mutate the caller's input.
• The order must remain unchanged, so sorting is invalid.

Why is it interesting?¶

It compresses subsequence dynamic programming from one state per index to one state per ending value, producing a linear-time solution.

Python solution¶

class Solution:
    def longestSubsequence(self, arr: list[int], difference: int) -> int:
        dp = {}
        best = 0

        for x in arr:
            # Any valid subsequence ending at x must extend one ending
            # at x - difference.
            dp[x] = dp.get(x - difference, 0) + 1
            best = max(best, dp[x])

        return best

• Time: \(O(n)\)
• Space: \(O(n)\)

Comment on my solution¶

The reverse-and-negate transformation is logically valid, but arr.reverse() unexpectedly modifies the input.

The main issues are:

• The nested search makes the worst-case time complexity \(O(n^2)\), causing the timeout.
• Extending the first matching tail is not always correct because it may choose a shorter chain.

For example, with arr = [2, 1, 2, 3, 4] and difference = 1, the implementation returns 3 instead of 4: the early singleton ending at 2 is extended before the longer subsequence [1, 2]. A dictionary fixes both issues by retaining only the greatest length for each ending value.

# Ideas:
# - [1,2,3,4], 1 -> 4
# - [1,5,7,8,5,3,4,2,1], -2 -> [7,5,3,1] -> 4
# - arithmetic subsequence
#   - a + diff = b
#   - b - a = diff
#   - a - b = -diff
# - (reversed(arr), -difference) gives the same result as (arr, difference)
#   - so we can reduce the problem to LIS with arithmetic constraint
# [1, 2, 4, 3, 5, 8, 7, 5, 1]
# 1 3 5 7
# 2 4
# 8

# WRONG
# Time Limit Exceeded: 34/41 testcases passed
class Solution:
    def longestSubsequence(self, arr: list[int], difference: int) -> int:
        if difference < 0:
            difference *= -1
            arr.reverse()
        tails = [] # [tail, length] of valid subsequences
        for x in arr:
            extended = False
            for i, (tail, length) in enumerate(tails):
                if x - tail == difference:
                    tails[i] = [x, length + 1]
                    extended = True
                    break
            if not extended:
                tails.append([x, 1])
        return max(length for _, length in tails)