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.
A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.
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 <= 105-104 <= arr[i], difference <= 104This approach uses a hash map (or dictionary) to keep track of the longest subsequence length that can be achieved ending with a specific value. For each element in the array, we check if there is an arithmetic subsequence ending with the element minus the given difference. If such a subsequence exists, we calculate the current subsequence length. Otherwise, we start a new subsequence from this element.
This Python solution uses a dictionary called dp where each key is a number from the array, and the value is the longest subsequence length ending with that number. We update the dictionary by iterating through each number in arr and deciding whether we can append the current number to an existing subsequence with the specified difference.
C++
JavaScript
Java
C
C#
Time Complexity: O(n), where n is the length of arr. We iterate over the array once.
Space Complexity: O(n), where n is the number of distinct elements in arr stored in the dictionary.
This approach utilizes an array to store information about each possible element value scaled according to the constraints. For each element in arr, determine if there is a previous subsequence that can be extended using direct array access.
This Python solution uses an indexed array to store the length of subsequences directly aligned by the values of elements. We handle negative indices by offsetting the array from the minimal possible value.
C++
JavaScript
Java
C
C#
Time Complexity: O(n), where n is the length of arr.
Space Complexity: O(1) (constant size array mentioned in constraints).
| Approach | Complexity |
|---|---|
| Dynamic Programming with HashMap | Time Complexity: O(n), where n is the length of arr. We iterate over the array once. |
| Optimized Dynamic Programming with Direct Indexing | Time Complexity: O(n), where n is the length of arr. |
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 views views
Watch 9 more video solutions →Practice Longest Arithmetic Subsequence of Given Difference with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor