Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1218.html
1218. Longest Arithmetic Subsequence of Given Difference
Level
Medium
Description
Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.
Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
1 <= arr.length <= 10^5-10^4 <= arr[i], difference <= 10^4
Solution
Use dynamic programming. Create an array subLengths of length arr.length, where subLengths[i] represents the length of the longest arithmetic subsequence with difference difference that ends at index i. Use a map to store each number and the last index that the number occurs. Initially, set subLengths[0] = 1 and put the key-value pair (arr[0], 0) into the map.
Loop over arr starting from index 1. At each index i, obtain the number at index i and the previous number in the arithmetic subsequence. If the previous number exists in the key set of the map, then obtain the previous number’s index prevIndex and the previous subsequence length subLengths[prevIndex], set subLengths[i] = subLengths[prevIndex] + 1, and update the maximum length of arithmetic subsequence as well. If the previous number does not exist in the key set of the map, then simply set subLengths[i] = 1. For each index i, put the key-value pair (arr[i], i) into the map.
Finally, return the maximum length of arithmetic subsequence.
-
class Solution { public int longestSubsequence(int[] arr, int difference) { int length = arr.length; int[] subLengths = new int[length]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); subLengths[0] = 1; map.put(arr[0], 0); int max = 1; for (int i = 1; i < length; i++) { int num = arr[i]; int prevNum = num - difference; if (map.containsKey(prevNum)) { int prevIndex = map.get(prevNum); subLengths[i] = subLengths[prevIndex] + 1; max = Math.max(max, subLengths[i]); } else subLengths[i] = 1; map.put(num, i); } return max; } } -
// OJ: https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/ // Time: O(N) // Space: O(N) class Solution { public: int longestSubsequence(vector<int>& A, int difference) { unordered_map<int, int> m; int ans = 0; for (int n : A) { int prev = n - difference; if (m.count(prev)) { m[n] = m[prev] + 1; if (n != prev) m.erase(prev); } else if (m.count(n) == 0) m[n] = 1; ans = max(ans, m[n]); } return ans; } }; -
class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: dp, ans = defaultdict(int), 1 for num in arr: dp[num] = dp[num - difference] + 1 ans = max(ans, dp[num]) return ans ############ # 1218. Longest Arithmetic Subsequence of Given Difference # https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/ class Solution: def longestSubsequence(self, arr: List[int], difference: int): mp = collections.defaultdict(int) for num in arr: mp[num] = 1 if num - difference not in mp else mp[num-difference] + 1 return max(mp.values()) -
func longestSubsequence(arr []int, difference int) int { dp, ans := make(map[int]int), 1 for _, num := range arr { dp[num] = dp[num-difference] + 1 ans = max(ans, dp[num]) } return ans } func max(a, b int) int { if a > b { return a } return b } -
/** * @param {number[]} arr * @param {number} difference * @return {number} */ var longestSubsequence = function (arr, difference) { let ans = 1; const dp = new Map(); for (const v of arr) { dp.set(v, (dp.get(v - difference) || 0) + 1); ans = Math.max(ans, dp.get(v)); } return ans; };