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
PreRequisite
What is an Arithmetic Subsequence ?
During highschool 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 (lastindex of our chain and maxlength) 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 2D Array based solution  go ahead ðŸ˜„
We will have a default length of 2 for each pair!
 iteration i=1
 j=2 > 42 > 2, (2, 2)
 j=3 > 72 > 5, (3, 2)
 j=4 > 92 > 7, (4, 2)
 j=5 > 102 > 8, (5, 2)
 iteration i=2
 j=3 > 74 > 3, (3, 2)

j=4 > 94 > 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 > 104 > 6, (5, 2)
 iteration i=3

j=4 > 97 > 2, (2, 2) (4, 2)

j=5 > 107 > 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 > 109 > 1, (5, 1)
 so the maximum length is 3!
 j=5 > 109 > 1, (5, 1)

Top comments (0)