Longest Arithmetic Subsequence - Leetcode Solution

The Longest Arithmetic Subsequence problem on LeetCode is a dynamic programming problem that requires us to find the length of the longest arithmetic subsequence in an array. An arithmetic subsequence is a sequence of numbers where the difference between any two consecutive numbers is the same.

Problem Statement

Given an array nums of n integers, return the length of the longest arithmetic subsequence in nums.

A subtype of dynamic programming called Memoization can be used to solve this problem.

Solution

In the memoization approach, we use a 2D array dp of size n*n, where n is the length of the given array. dp[i][j] denotes the length of the longest arithmetic subsequence ending at index i and with a difference of j.

Initially, we set all values of dp to 2 because any two elements in an array form an arithmetic sequence of length 2.

To find a longer subsequence in the array, we iterate through the array and for each element, we check if there is an element before it that has a difference of j, where j is the difference between the current element and the previous one (nums[i] - nums[k]). If there is such an element, then we add 1 to the length of the arithmetic subsequence ending at i with difference j.

At the end of the iteration, the maximum value in the dp array is the length of the longest arithmetic subsequence in the array.

Code

Here's the python implementation for the memoization approach:

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[2]*n for _ in range(n)]
        max_len = 2
        
        for i in range(n):
            for j in range(i+1, n):
                diff = nums[j] - nums[i]
                for k in range(i):
                    if nums[i] - nums[k] == diff:
                        dp[i][j] = max(dp[i][j], dp[k][i] + 1)
                        max_len = max(max_len, dp[i][j])
        
        return max_len

The time complexity of this solution is O(n^3) and the space complexity is O(n^2), where n is the length of the given array.

To optimize the time complexity to O(n^2), we can use a hashmap to store the indices of each element in the array and reduce the third loop of k in the above code to a hashmap look up.

Here's the optimized python implementation:

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[2]*n for _ in range(n)]
        indices = {nums[i]: i for i in range(n)}
        max_len = 2
        
        for i in range(n):
            for j in range(i+1, n):
                diff = nums[j] - nums[i]
                if nums[i] - diff in indices:
                    k = indices[nums[i] - diff]
                    dp[i][j] = max(dp[i][j], dp[k][i] + 1)
                    max_len = max(max_len, dp[i][j])
        
        return max_len

With this optimization, the time complexity is reduced to O(n^2).

1