Leetcode: Longest Arithmetic Subsequence

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #1027 (Medium): Longest Arithmetic Subsequence

1027. Longest Arithmetic Subsequence

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

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], ..., nums[ik] with 0 <= i1 < i2 < ... < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].

Constraints:

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Pre-Requisite

What is an Arithmetic Subsequence ?

During high-school we learnt this concept with another name **Arithmetic Progression (AP)*.
The idea is pretty simple a sequence of numbers is called an AP if there are at least 3 numbers and they are equidistant from each other!

so, 1 8 15 is an AP as 1 (+7) 8 (+7) 15, we have a difference of 7 and so if I were to ask you what number would come next - what would you say?

• 22 ?

Also did you notice an interesting fact here - in a sorted list 1 + 15 = 2 x 8 -> the middle number when doubled is equal to the sum of its neighbours! DO NOT FORGET THIS 😉

Solution

So we know how to recognize an AP, but how do we find the longest AP, also consider these variations

• The AP can have negative numbers
  • -1 2 5 8 is a valid AP
• The AP can be unordered (not sorted)
  • 5 9 1 is a valid AP = 1 5 9
• The AP subsequence
  • 5 4 9 1 has a valid AP subsequence -> 1 5 9

ok so let take one example:
9 4 7 2 10

One way to look at the solution is to first sort them
2 4 7 9 10 -> can you see the AP Subsequence ?
4 7 10 - here the length is 3 and the difference is also 3

note 2,4 and 7,9 is not a valid AP even though they share the same difference. But for this problem we can say it has a length of 2 each with difference is also 2.

Figuring out the algorithm

Naturally when we see the maximization or minimization problem what we want is to compare ALL results and return the max or min. We will need Dynamic Programming concepts here!

If you see the example above, can we say the difference is out key and a pair of (last-index of our chain and max-length) is our value ?

• why do you need a pair as value? say we have another example 1 2 14 15 16 27 29 30 43
  how many AP's do we have:
  • diff = 14 [1 15 29]
  • diff = 14 [1 15 29 43]
  • diff = 13 [1 14 27]
  • diff = 14 [2 16 30]

as you can notice we have same difference but one pair of 14 has the most numbers 1 15 29 43

so if we store the DP values as a map of map with difference as key - maybe the problem is not that difficult!

Lets see the code

Implementation

    public int longestArithSeqLength(int[] nums) {
        int size = nums.length;
        // Stores the length of sequences having same difference
        Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();

        // Stores the resultant length
        int res = 2;

        // Iterate over the array
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {

                // our dp key is diff
                int diff = nums[j] - nums[i];

                 // here we store the pair of last index which gives us max difference
                Map<Integer, Integer> temp = new HashMap<>();

                // Update length of subsequence
                if (dp.containsKey(diff)) {
                    temp = dp.get(diff);

                    if (temp.containsKey(i)) {
                        temp.put(j, temp.get(i) + 1);
                    }
                }

                temp.putIfAbsent(j, 2);

                dp.put(diff, temp);
                res = Math.max(res, temp.get(j));
            }
        }

        return res;
    }

Analysis

As you can see this solution is not the most complicated one, I found it easier to think to almost completion during an interview without knowing anything about AP beforehand.

If you take it upon you to use some 2-D Array based solution - go ahead 😄

We will have a default length of 2 for each pair!

iteration i=1
• j=2 -> 4-2 -> 2, (2, 2)
• j=3 -> 7-2 -> 5, (3, 2)
• j=4 -> 9-2 -> 7, (4, 2)
• j=5 -> 10-2 -> 8, (5, 2)
  iteration i=2
  • j=3 -> 7-4 -> 3, (3, 2)

  • j=4 -> 9-4 -> 5, (3, 2) (4, 2)this is interesting we already have 5 as key, but when we picked the pair we don't have 2nd index as key - so we added a new pair for value set[2,7][4,9]

  • j=5 -> 10-4 -> 6, (5, 2)
    iteration i=3

    • j=4 -> 9-7 -> 2, (2, 2) (4, 2)

    • j=5 -> 10-7 -> 3, (3, 2) (5, 3)` this is interesting we already have 5 as key, so we will update its existing length to +1
      
      

      iteration i=4
      • j=5 -> 10-9 -> 1, (5, 1)
        • so the maximum length is 3!