Vultr DocsLatest Content

Longest Arithmetic Subsequence of Given Difference

Updated on 03 June, 2025
Longest Arithmetic Subsequence of Given Difference header image

Problem Statement

In this challenge, you are tasked to identify the length of the longest subsequence within a given array arr, such that this subsequence is an arithmetic sequence with a consistent difference known as difference between consecutive elements. An arithmetic sequence is a sequence of numbers with a specific interval between every adjacent pair.

A subsequence is a derived sequence from the original array arr where certain elements may be omitted but the relative order of the remaining elements is preserved.

Examples

Example 1

Input:

arr = [1,2,3,4], difference = 1

Output:

4

Explanation:

The longest arithmetic subsequence is [1,2,3,4] with a difference of 1.

Example 2

Input:

arr = [1,3,5,7], difference = 1

Output:

1

Explanation:

No two numbers differ by 1, so the longest arithmetic subsequence is any single number.

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], where each consecutive element differs by -2.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i], difference <= 10^4

Approach and Intuition

We aim to find the longest subsequence in arr such that the difference between every two consecutive elements equals difference. Given the large input size, a brute-force approach checking every subsequence is infeasible.

Optimized Approach (Dynamic Hash Mapping):

  1. Initialize a dictionary dp where dp[x] stores the length of the longest arithmetic subsequence ending with value x.
  2. Iterate through each element x in arr.
  3. For each x, compute prev = x - difference.
  4. If prev exists in dp, then x can extend the sequence ending at prev. So, dp[x] = dp[prev] + 1.
  5. If prev does not exist, start a new sequence: dp[x] = 1.
  6. Track and return the maximum value from dp.values().

Time Complexity:

  • O(n), where n is the length of arr, since each element is processed once.

This method ensures the solution is efficient, even for large arrays, and capitalizes on the properties of arithmetic sequences combined with hash-based dynamic tracking.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int longestSubsequence(vector<int>& sequence, int diff) {
        unordered_map<int, int> sequenceDP;
        int maxLen = 1;
            
        for (int value : sequence) {
            int priorValue = sequenceDP.count(value - diff) ? sequenceDP[value - diff] : 0;
            sequenceDP[value] = priorValue + 1;
            maxLen = max(maxLen, sequenceDP[value]);
        }
            
        return maxLen;
    }
};

This C++ solution addresses the problem of finding the longest arithmetic subsequence in an array where each pair of consecutive elements has a given difference. The method employed utilizes dynamic programming (DP) to efficiently compute the solution. The use of an unordered map sequenceDP tracks the length of the arithmetic subsequences each element can form.

To solve the problem:

  • Initialize maxLen to 1, which is the smallest possible length of any subsequence, and sequenceDP to store the lengths of the subsequences.
  • Iterate through each element value in the array sequence.
  • For each value, compute priorValue, which is the subsequence length from the previous element (i.e., value - diff) if it exists in sequenceDP.
  • Update sequenceDP[value] by adding 1 to priorValue. This step essentially extends the subsequence ending with the previous element to include the current element.
  • Update maxLen to keep track of the maximum subsequence length encountered so far.

The final value of maxLen represents the length of the longest arithmetic subsequence with the given difference. By leveraging dynamic programming with a hash map, this approach ensures an efficient solution that avoids the quadratic time complexity of naive methods.

java 
class Solution {
    public int maxSubsequenceLength(int[] sequence, int diff) {
        Map<Integer, Integer> lengthMap = new HashMap<>();
        int maxLength = 1;
    
        for (int num : sequence) {
            int prevLength = lengthMap.getOrDefault(num - diff, 0);
            lengthMap.put(num, prevLength + 1);
            maxLength = Math.max(maxLength, lengthMap.get(num));
        }
    
        return maxLength;
    }
}

This guide covers how to find the longest arithmetic subsequence of a given difference in an array of integers using Java. The provided method, maxSubsequenceLength, achieves this by employing a HashMap to track the lengths of subsequences ending at each element in the sequence.

  • Initialize a HashMap named lengthMap where keys represent numbers from the array and values represent the maximum subsequence length ending at that number.
  • Set maxLength to 1, which accounts for the minimum possible subsequence length.
  • Loop through each integer num in the sequence array:
    • Compute prevLength using the HashMap for the number num minus the given diff. If not found in the map, default to 0.
    • Update the lengthMap for the number num to prevLength + 1.
    • Update maxLength whenever a longer subsequence is found by comparing the current value with the value stored in lengthMap for num.
  • Return maxLength, which now contains the length of the longest arithmetic subsequence with the given difference.

This solution adeptly leverages the HashMap data structure to store interim results, effectively reducing the computational complexity in comparison to the naive approach, making it efficient for larger datasets.

python 
class Solution:
    def longestSubseq(self, sequence: List[int], diff: int) -> int:
        memo = {}
        max_length = 1
        for number in sequence:
            prev_val = memo.get(number - diff, 0)
            memo[number] = prev_val + 1
            max_length = max(max_length, memo[number])
            
        return max_length

This Python solution tackles the problem of finding the longest arithmetic subsequence in an array with a given difference. Utilize a dictionary memo to store sequences with the number as the key and the sequence length as the value. As you iterate through each number in sequence, compute the previous number number - diff and fetch its value from memo with a default of 0. Store or update the current number's sequence length in memo by incrementing the fetched value. Simultaneously, update max_length to ensure it holds the value of the longest found subsequence at any point. Return max_length as the desired result, reflecting the length of the longest arithmetic subsequence for the provided difference. This approach ensures efficiency by avoiding redundant recalculations.

Comments