29
loading...
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.
If you liked this solution or found it useful, please like this post.
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
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!
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?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 😉
So we know how to recognize an AP, but how do we find the longest AP, also consider these variations
-
-1 2 5 8is a valid AP
-
5 9 1is a valid AP =1 5 9
-
5 4 9 1has a valid AP subsequence ->1 5 9
ok so let take one example:
9 4 7 2 10One 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 3note 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.
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 ?
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 43so 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
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;
}
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!
- j=5 -> 10-9 -> 1, (5, 1)
-
29