< Back





1027. Longest Arithmetic Subsequence

Similar to our other subsequence problems, but with a bit of a twist when it comes to memoizing our
solutions. We're asked to find the longest arithmetic subsequence, such that all members of the
subsequence have the same difference, i.e. for all i, seq[i + 1] - seq[i] is the same value.

In previous subsequence problems with an arithmetic difference, we not that the desired difference
is provided to us. This makes it easier to store our memoization dictionary. In this instance, for
each index / value, we have to record all the subsequences that can be created up to this point, i,
for a particular difference. Thus, the dictionary will be indexed with a tuple of values:

  * T[(i, diff)]

Where diff is the difference between two numbers, e.g. nums[i] and nums[j]. Instead of looking
forward for our next member of the subsequence, for each number i, we'll look back to front using j,
where j will iterate from 0 to i. Each number, j, we will already have recorded the subsequences
that end at j, as well as the difference between the numbers in the subsequence. Therefore, if the
number i can be appended to one of j's subsequences, because their differences are the same, we
reuse the recorded length of the existing subsequence and append i to it.

The solution is as follows:


  class Solution:
      def longestArithSeqLength(self, nums: List[int]) -> int:
          n, T = len(nums), defaultdict(int)

          for i in range(n):
              x = nums[i]

              for j in range(i):
                  diff = x - nums[j]
                  T[(i, diff)] = T[(j, diff)] + 1

          return max(T.values()) + 1


_ Time Complexity:

  O(n^2) - At each index i, we iterate from 0 to i - n is the length of the input.

_ Space Complexity:

  O(n^2) - We store all subsequences in a dictionary.