# Longest Arithmetic Subsequence of Given Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference)
Canonical: https://scaleengineer.com/dsa/problems/longest-arithmetic-subsequence-of-given-difference
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
---
## Problem
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 <= 104`

# Approaches
## Brute Force Iteration
This approach iterates through every element of the array, considering each as a potential starting point for an arithmetic subsequence. For each starting element, it scans the rest of the array to find subsequent elements that fit the arithmetic progression with the given difference. It's a straightforward brute-force method.
**Time:** O(N^2), where N is the number of elements in `arr`. The nested loops lead to a quadratic time complexity, as for each element, we potentially scan the rest of the array. · **Space:** O(1), as we only use a few variables to store the current state, regardless of the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space, making it memory efficient.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits.
### Explanation
The brute-force strategy involves a nested loop structure. The outer loop selects a starting element for a subsequence. The inner loop then traverses the remainder of the array to find the next elements that maintain the required `difference`. We keep track of the longest such subsequence found starting from any element.

```java
class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            int currentLength = 1;
            int lastElement = arr[i];
            for (int j = i + 1; j < n; j++) {
                if (arr[j] == lastElement + difference) {
                    currentLength++;
                    lastElement = arr[j];
                }
            }
            maxLength = Math.max(maxLength, currentLength);
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize a variable `maxLength` to 1.
2. Iterate through the input array `arr` with an index `i` from `0` to `n-1`.
3. For each `i`, consider `arr[i]` as the start of a potential subsequence. Initialize `currentLength = 1` and `lastElement = arr[i]`.
4. Start a nested loop with index `j` from `i+1` to `n-1`.
5. Inside the nested loop, check if `arr[j]` is equal to `lastElement + difference`.
6. If it is, increment `currentLength` and update `lastElement` to `arr[j]`.
7. After the inner loop finishes, update `maxLength` with the maximum of `maxLength` and `currentLength`.
8. After the outer loop finishes, return `maxLength`.

## Dynamic Programming (Tabulation)
This approach uses dynamic programming to solve the problem. We define a DP array, `dp`, where `dp[i]` stores the length of the longest arithmetic subsequence that ends with the element `arr[i]`. To compute `dp[i]`, we look at all previous elements `arr[j]` (where `j < i`) to see if `arr[i]` can extend a subsequence ending at `arr[j]`.
**Time:** O(N^2), due to the nested loops required to iterate through all pairs of elements `(i, j)` where `j < i`. · **Space:** O(N), for the `dp` array used to store the lengths of subsequences ending at each index.
**Pros:** Introduces a structured DP approach that can be optimized.; Guaranteed to find the correct solution.
**Cons:** The O(N^2) time complexity is too slow for the given constraints and will not pass.; Uses O(N) space, which is less efficient than the brute-force O(1) space complexity.
### Explanation
The state `dp[i]` represents the length of the longest arithmetic subsequence ending at index `i`. To calculate this, we must find a previous index `j < i` such that `arr[j] = arr[i] - difference`. If such a `j` exists, we can extend the subsequence ending at `j`, so `dp[i]` becomes `dp[j] + 1`. We check all possible `j`'s and take the one that gives the maximum length.

```java
import java.util.Arrays;

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] == arr[j] + difference) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }
}
```
### Algorithm
1. Create a DP array `dp` of the same size as the input array `arr`.
2. Initialize all elements of `dp` to 1, as each element itself is a subsequence of length 1.
3. Initialize a variable `maxLength` to 1.
4. Iterate through the array `arr` with an index `i` from `0` to `n-1`.
5. For each `i`, start a nested loop with index `j` from `0` to `i-1`.
6. Inside the inner loop, check if `arr[i] == arr[j] + difference`.
7. If true, it means `arr[i]` can extend the subsequence ending at `arr[j]`. Update `dp[i] = Math.max(dp[i], 1 + dp[j])`.
8. After the inner loop, update `maxLength = Math.max(maxLength, dp[i])`.
9. After the outer loop completes, return `maxLength`.

## Optimized Dynamic Programming with Hash Map
This is the most efficient approach, optimizing the O(N^2) DP solution by using a hash map. Instead of storing DP states by index, we store them by value. The hash map keeps track of the length of the longest arithmetic subsequence ending with a particular number encountered so far. This allows us to find the length of the preceding subsequence in O(1) average time, avoiding the costly inner loop.
**Time:** O(N), where N is the length of `arr`. We iterate through the array once, and each hash map operation (get, put) takes, on average, O(1) time. · **Space:** O(N) in the worst case. The hash map might store an entry for each unique element in the array.
**Pros:** Highly efficient with a linear time complexity.; Passes the given constraints with ease.
**Cons:** Uses extra space for the hash map, which can be up to O(N) if all elements are unique.
### Explanation
The key insight is that to calculate the length of a subsequence ending with `arr[i]`, we only need to know the length of a subsequence ending with the value `arr[i] - difference`. A hash map is a perfect data structure for this, mapping values to lengths. As we iterate through the array, we query the map for the previous element's subsequence length and update the map with the current element's subsequence length.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> dp = new HashMap<>();
        int maxLength = 1;
        for (int num : arr) {
            // Find the length of the subsequence ending with the previous number.
            int prevLength = dp.getOrDefault(num - difference, 0);
            // The current subsequence length is the previous one plus 1.
            int currentLength = prevLength + 1;
            // Store the length of the subsequence ending with the current number.
            dp.put(num, currentLength);
            // Update the overall maximum length found so far.
            maxLength = Math.max(maxLength, currentLength);
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize a hash map, `dp`, to store the lengths of subsequences ending with a specific number.
2. Initialize `maxLength` to 1.
3. Iterate through each number `num` in the input array `arr`.
4. For each `num`, calculate the value of the required previous element: `prevNum = num - difference`.
5. Look up `prevNum` in the hash map to get the length of the subsequence ending with it. If not found, this length is 0. Let this be `prevLength`.
6. The length of the new subsequence ending with `num` is `currentLength = prevLength + 1`.
7. Update the hash map with this new length: `dp.put(num, currentLength)`.
8. Update the overall `maxLength = Math.max(maxLength, currentLength)`.
9. After iterating through all numbers, return `maxLength`.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} arr * @param {number} difference * @return {number} */ var longestSubsequence =
  function (arr, difference) {
    const f = new Map();
    for (const x of arr) {
      f.set(x, (f.get(x - difference) || 0) + 1);
    }
    return Math.max(...f.values());
  };

```

### Java

```java
class Solution {
public
  int longestSubsequence(int[] arr, int difference) {
    Map<Integer, Integer> f = new HashMap<>();
    int ans = 0;
    for (int x : arr) {
      f.put(x, f.getOrDefault(x - difference, 0) + 1);
      ans = Math.max(ans, f.get(x));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestSubsequence(vector<int> &arr, int difference) {
    unordered_map<int, int> f;
    int ans = 0;
    for (int x : arr) {
      f[x] = f[x - difference] + 1;
      ans = max(ans, f[x]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int: f = defaultdict(int) for x in arr: f[x] = f[x - difference] + 1 return max(f . values())

```