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

Number: 1087

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Adobe, Uber, Snapdeal

Problem Description

Given an array of integers, the goal is to find the length of the longest arithmetic subsequence in the array. A subsequence is derived from the original array by deleting some or no elements without changing the order. An arithmetic sequence means that the differences between consecutive elements are the same.

Key Insights

  • Use dynamic programming where dp[i][diff] represents the length of the longest arithmetic subsequence ending at index i with difference diff.
  • For every pair of indices (j, i) with j < i, compute the difference diff = nums[i] - nums[j].
  • If there exists a subsequence ending at j with the same difference, extend it; otherwise, start a new subsequence with length 2.
  • Finally, keep track of the maximum subsequence length encountered.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of elements in the array. Space Complexity: O(n^2) in the worst case due to storing differences for each index.

Solution

We iterate over the array with a nested loop. For each pair (j, i), we calculate the difference diff = nums[i] - nums[j] and update our dp array: if there is an entry dp[j][diff], then dp[i][diff] = dp[j][diff] + 1; otherwise, dp[i][diff] is set to 2 (since any two numbers form an arithmetic sequence). The answer is the maximum value in our dp structure. We use a hash table (dictionary) for each index to store the counts of arithmetic subsequences by their common difference.

Code Solutions

# Python solution for Longest Arithmetic Subsequence
def longestArithSeqLength(nums):
    # n is the length of the input array
    n = len(nums)
    # dp will be a list of dictionaries.
    # dp[i] will store {diff: length} for subsequences ending at index i
    dp = [{} for _ in range(n)]
    max_length = 0  # initialize max length
    
    # iterate over each pair (j, i) where j < i
    for i in range(n):
        for j in range(i):
            # current difference between nums[i] and nums[j]
            diff = nums[i] - nums[j]
            # get the length for this difference from dp[j], default is 1 (only nums[j])
            dp[i][diff] = dp[j].get(diff, 1) + 1
            # update the maximum length found so far
            max_length = max(max_length, dp[i][diff])
    
    return max_length

# Example usage:
# print(longestArithSeqLength([3,6,9,12])) -> Output: 4
← Back to All Questions