Longest Arithmetic Subsequence of Given Difference

Med

#1137Time: O(N^2), where N is the number of elements in `arr`. The nested loops lead to a quadratic time complexity, as for each element, we potentially scan the rest of the array.Space: O(1), as we only use a few variables to store the current state, regardless of the input size.

Patterns

Dynamic Programming

Data structures

Array Hash Table

Prompt

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 <= 10⁵
-10⁴ <= arr[i], difference <= 10⁴

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through every element of the array, considering each as a potential starting point for an arithmetic subsequence. For each starting element, it scans the rest of the array to find subsequent elements that fit the arithmetic progression with the given difference. It's a straightforward brute-force method.

Algorithm

Initialize a variable maxLength to 1.
Iterate through the input array arr with an index i from 0 to n-1.
For each i, consider arr[i] as the start of a potential subsequence. Initialize currentLength = 1 and lastElement = arr[i].
Start a nested loop with index j from i+1 to n-1.
Inside the nested loop, check if arr[j] is equal to lastElement + difference.
If it is, increment currentLength and update lastElement to arr[j].
After the inner loop finishes, update maxLength with the maximum of maxLength and currentLength.
After the outer loop finishes, return maxLength.

Walkthrough

The brute-force strategy involves a nested loop structure. The outer loop selects a starting element for a subsequence. The inner loop then traverses the remainder of the array to find the next elements that maintain the required difference. We keep track of the longest such subsequence found starting from any element.

1class Solution {2    public int longestSubsequence(int[] arr, int difference) {3        int n = arr.length;4        if (n == 0) {5            return 0;6        }7        int maxLength = 1;8        for (int i = 0; i < n; i++) {9            int currentLength = 1;10            int lastElement = arr[i];11            for (int j = i + 1; j < n; j++) {12                if (arr[j] == lastElement + difference) {13                    currentLength++;14                    lastElement = arr[j];15                }16            }17            maxLength = Math.max(maxLength, currentLength);18        }19        return maxLength;20    }21}

Complexity

Time

O(N^2), where N is the number of elements in `arr`. The nested loops lead to a quadratic time complexity, as for each element, we potentially scan the rest of the array.

Space

O(1), as we only use a few variables to store the current state, regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Uses constant extra space, making it memory efficient.

Cons

Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits.

This approach uses dynamic programming to solve the problem. We define a DP array, dp, where dp[i] stores the length of the longest arithmetic subsequence that ends with the element arr[i]. To compute dp[i], we look at all previous elements arr[j] (where j < i) to see if arr[i] can extend a subsequence ending at arr[j].

Algorithm

Create a DP array dp of the same size as the input array arr.
Initialize all elements of dp to 1, as each element itself is a subsequence of length 1.
Initialize a variable maxLength to 1.
Iterate through the array arr with an index i from 0 to n-1.
For each i, start a nested loop with index j from 0 to i-1.
Inside the inner loop, check if arr[i] == arr[j] + difference.
If true, it means arr[i] can extend the subsequence ending at arr[j]. Update dp[i] = Math.max(dp[i], 1 + dp[j]).
After the inner loop, update maxLength = Math.max(maxLength, dp[i]).
After the outer loop completes, return maxLength.

Walkthrough

The state dp[i] represents the length of the longest arithmetic subsequence ending at index i. To calculate this, we must find a previous index j < i such that arr[j] = arr[i] - difference. If such a j exists, we can extend the subsequence ending at j, so dp[i] becomes dp[j] + 1. We check all possible j's and take the one that gives the maximum length.

1import java.util.Arrays;2 3class Solution {4    public int longestSubsequence(int[] arr, int difference) {5        int n = arr.length;6        if (n == 0) {7            return 0;8        }9        int[] dp = new int[n];10        Arrays.fill(dp, 1);11        int maxLength = 1;12        for (int i = 0; i < n; i++) {13            for (int j = 0; j < i; j++) {14                if (arr[i] == arr[j] + difference) {15                    dp[i] = Math.max(dp[i], 1 + dp[j]);16                }17            }18            maxLength = Math.max(maxLength, dp[i]);19        }20        return maxLength;21    }22}

Complexity

Time

O(N^2), due to the nested loops required to iterate through all pairs of elements `(i, j)` where `j < i`.

Space

O(N), for the `dp` array used to store the lengths of subsequences ending at each index.

Trade-offs

Pros

Introduces a structured DP approach that can be optimized.
Guaranteed to find the correct solution.

Cons

The O(N^2) time complexity is too slow for the given constraints and will not pass.
Uses O(N) space, which is less efficient than the brute-force O(1) space complexity.

This is the most efficient approach, optimizing the O(N^2) DP solution by using a hash map. Instead of storing DP states by index, we store them by value. The hash map keeps track of the length of the longest arithmetic subsequence ending with a particular number encountered so far. This allows us to find the length of the preceding subsequence in O(1) average time, avoiding the costly inner loop.

Algorithm

Initialize a hash map, dp, to store the lengths of subsequences ending with a specific number.
Initialize maxLength to 1.
Iterate through each number num in the input array arr.
For each num, calculate the value of the required previous element: prevNum = num - difference.
Look up prevNum in the hash map to get the length of the subsequence ending with it. If not found, this length is 0. Let this be prevLength.
The length of the new subsequence ending with num is currentLength = prevLength + 1.
Update the hash map with this new length: dp.put(num, currentLength).
Update the overall maxLength = Math.max(maxLength, currentLength).
After iterating through all numbers, return maxLength.

Walkthrough

The key insight is that to calculate the length of a subsequence ending with arr[i], we only need to know the length of a subsequence ending with the value arr[i] - difference. A hash map is a perfect data structure for this, mapping values to lengths. As we iterate through the array, we query the map for the previous element's subsequence length and update the map with the current element's subsequence length.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int longestSubsequence(int[] arr, int difference) {6        Map<Integer, Integer> dp = new HashMap<>();7        int maxLength = 1;8        for (int num : arr) {9            // Find the length of the subsequence ending with the previous number.10            int prevLength = dp.getOrDefault(num - difference, 0);11            // The current subsequence length is the previous one plus 1.12            int currentLength = prevLength + 1;13            // Store the length of the subsequence ending with the current number.14            dp.put(num, currentLength);15            // Update the overall maximum length found so far.16            maxLength = Math.max(maxLength, currentLength);17        }18        return maxLength;19    }20}

Complexity

Time

O(N), where N is the length of `arr`. We iterate through the array once, and each hash map operation (get, put) takes, on average, O(1) time.

Space

O(N) in the worst case. The hash map might store an entry for each unique element in the array.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Passes the given constraints with ease.

Cons

Uses extra space for the hash map, which can be up to O(N) if all elements are unique.

Solutions

Solution

1/** * @param {number[]} arr * @param {number} difference * @return {number} */ var longestSubsequence =2  function (arr, difference) {3    const f = new Map();4    for (const x of arr) {5      f.set(x, (f.get(x - difference) || 0) + 1);6    }7    return Math.max(...f.values());8  };

1class Solution {2public3  int longestSubsequence(int[] arr, int difference) {4    Map<Integer, Integer> f = new HashMap<>();5    int ans = 0;6    for (int x : arr) {7      f.put(x, f.getOrDefault(x - difference, 0) + 1);8      ans = Math.max(ans, f.get(x));9    }10    return ans;11  }12}

1class Solution {2public:3  int longestSubsequence(vector<int> &arr, int difference) {4    unordered_map<int, int> f;5    int ans = 0;6    for (int x : arr) {7      f[x] = f[x - difference] + 1;8      ans = max(ans, f[x]);9    }10    return ans;11  }12};

1class Solution:2    def longestSubsequence(self, arr: List[int], difference: int) -> int: f = defaultdict(int) for x in arr: f[x] = f[x - difference] + 1 return max(f . values())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/** * @param {number[]} arr * @param {number} difference * @return {number} */ var longestSubsequence =2  function (arr, difference) {3    const f = new Map();4    for (const x of arr) {5      f.set(x, (f.get(x - difference) || 0) + 1);6    }7    return Math.max(...f.values());8  };

1class Solution {2public3  int longestSubsequence(int[] arr, int difference) {4    Map<Integer, Integer> f = new HashMap<>();5    int ans = 0;6    for (int x : arr) {7      f.put(x, f.getOrDefault(x - difference, 0) + 1);8      ans = Math.max(ans, f.get(x));9    }10    return ans;11  }12}

1class Solution {2public:3  int longestSubsequence(vector<int> &arr, int difference) {4    unordered_map<int, int> f;5    int ans = 0;6    for (int x : arr) {7      f[x] = f[x - difference] + 1;8      ans = max(ans, f[x]);9    }10    return ans;11  }12};

1class Solution:2    def longestSubsequence(self, arr: List[int], difference: int) -> int: f = defaultdict(int) for x in arr: f[x] = f[x - difference] + 1 return max(f . values())

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.