Problem Description

You are given an integer array arr and an integer difference. Your task is to find the length of the longest subsequence in arr such that the difference between adjacent elements in the subsequence is exactly 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. Elements cannot be reused.

Constraints:

• 1 ≤ arr.length ≤ 10⁵
• -10⁴ ≤ arr[i], difference ≤ 10⁴

The solution must be efficient enough to handle large input sizes.

Thought Process

At first glance, we might consider checking all possible subsequences and filtering those that form an arithmetic sequence with the given difference. However, generating all subsequences is computationally infeasible for large arrays.

Instead, we notice that for each element, if we know the length of the longest valid subsequence ending with arr[i] - difference, we can extend it by including arr[i]. This suggests a dynamic programming or hash map approach, where we "build up" the answer as we traverse the array.

The key insight is to efficiently track, for every possible value, the length of the longest subsequence ending at that value. This avoids redundant work and lets us process the array in a single pass.

Solution Approach

To solve the problem efficiently, we use a hash map (dictionary) to keep track of the length of the longest arithmetic subsequence ending at each value.

1. Initialize an empty hash map dp. For any value x, dp[x] stores the length of the longest subsequence ending at x.
2. Iterate through each number num in arr:
   • Check if num - difference exists in dp. If it does, set dp[num] = dp[num - difference] + 1.
   • If not, start a new subsequence at num by setting dp[num] = 1.
3. Keep track of the maximum value in dp throughout the iteration. This will be the answer.

Why a hash map? Because it allows O(1) access to the subsequence length for any value, which is crucial for efficiency.

Example Walkthrough

Input: arr = [1, 5, 7, 8, 5, 3, 4, 2, 1], difference = -2

Let's process the array step by step:

• 1: 1 - (-2) = 3 not in dp. Start new: dp[1] = 1
• 5: 5 - (-2) = 7 not in dp. Start new: dp[5] = 1
• 7: 7 - (-2) = 9 not in dp. Start new: dp[7] = 1
• 8: 8 - (-2) = 10 not in dp. Start new: dp[8] = 1
• 5: 5 - (-2) = 7 in dp (dp[7]=1): dp[5] = 2
• 3: 3 - (-2) = 5 in dp (dp[5]=2): dp[3] = 3
• 4: 4 - (-2) = 6 not in dp. Start new: dp[4] = 1
• 2: 2 - (-2) = 4 in dp (dp[4]=1): dp[2] = 2
• 1: 1 - (-2) = 3 in dp (dp[3]=3): dp[1] = 4

The maximum value in dp is 4, corresponding to the subsequence [7, 5, 3, 1].

Time and Space Complexity

Brute-force approach:

• Would involve generating all subsequences, which is O(2ⁿ) and infeasible for large n.

• Time Complexity: O(n), since we process each element once and hash map operations are O(1) on average.
• Space Complexity: O(n), in the worst case where all numbers are unique and stored in the hash map.

This efficiency makes the approach suitable for large input sizes.

Summary

By recognizing that the problem reduces to tracking the longest subsequence ending at each value, and using a hash map to do so efficiently, we avoid brute-force enumeration. This dynamic programming approach ensures that we only need a single pass through the array, making the solution both elegant and performant.

The main insight is to "build up" the answer for each value based on previously seen values, leveraging constant-time hash map lookups for maximum efficiency.

Code Implementation

class Solution:
    def longestSubsequence(self, arr, difference):
        dp = {}
        maxlen = 0
        for num in arr:
            prev = num - difference
            dp[num] = dp.get(prev, 0) + 1
            maxlen = max(maxlen, dp[num])
        return maxlen
      

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> dp;
        int maxlen = 0;
        for (int num : arr) {
            int prev = num - difference;
            dp[num] = dp.count(prev) ? dp[prev] + 1 : 1;
            maxlen = max(maxlen, dp[num]);
        }
        return maxlen;
    }
};
      

import java.util.HashMap;

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer, Integer> dp = new HashMap<>();
        int maxlen = 0;
        for (int num : arr) {
            int prev = num - difference;
            int currLen = dp.getOrDefault(prev, 0) + 1;
            dp.put(num, currLen);
            maxlen = Math.max(maxlen, currLen);
        }
        return maxlen;
    }
}
      

var longestSubsequence = function(arr, difference) {
    const dp = new Map();
    let maxlen = 0;
    for (const num of arr) {
        const prev = num - difference;
        const currLen = (dp.get(prev) || 0) + 1;
        dp.set(num, currLen);
        maxlen = Math.max(maxlen, currLen);
    }
    return maxlen;
};