We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Arithmetic Subsequence of Given Difference

Number: 1330

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given an integer array and a target difference, find the length of the longest subsequence in the array such that the difference between adjacent elements is exactly the given value. A subsequence can skip elements but must maintain the original order.

Key Insights

  • Use dynamic programming to track the longest arithmetic subsequence ending at each number.
  • Use a hash table (dictionary or map) to efficiently retrieve and update the length of subsequences.
  • For each element, check if there exists a previous element equal to the current element minus the difference.
  • The answer is the maximum subsequence length tracked while processing the array.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, since we process each element once. Space Complexity: O(n), used by the hash table to store subsequence lengths for each unique element.

Solution

The solution uses a hash table (or dictionary/map) to keep track of the longest arithmetic subsequence that ends at a particular number. For every number in the array, the algorithm checks if there is a subsequence ending with the number that is exactly "difference" less. If so, the current number is added to that subsequence, increasing its length by 1. Otherwise, a new subsequence starting with the number is considered with length 1. The maximum subsequence length is updated accordingly throughout the iteration.

Code Solutions

# Function to determine the longest arithmetic subsequence with given difference.
def longestSubsequence(arr, difference):
    # Dictionary to store the longest subsequence length ending at a given number.
    dp = {}
    # Variable to track the maximum subsequence length.
    longest = 0
    
    # Iterate through each number in the array.
    for num in arr:
        # If there's a subsequence ending with (num - difference), extend that subsequence; otherwise, start with 1.
        dp[num] = dp.get(num - difference, 0) + 1
        # Update the maximum length found so far.
        longest = max(longest, dp[num])
    
    return longest

# Example usage:
if __name__ == "__main__":
    arr = [1,2,3,4]
    difference = 1
    print(longestSubsequence(arr, difference))  # Output: 4
← Back to All Questions