Problem

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.

Examples

Example 1:

1
2
3
4
5

Input:
arr = [1,2,3,4], difference = 1
Output:
 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

1
2
3
4
5

Input:
arr = [1,3,5,7], difference = 1
Output:
 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:

1
2
3
4
5

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].

Solution

Method 1 - Using DP

Intuition

For each number in the array, check if there is a previous number in the arithmetic sequence (current number minus difference). Use a hash map to store the length of the longest subsequence ending at each number. Update the map as you iterate.

Approach

Iterate through the array. For each element, set its subsequence length to one more than the length of the subsequence ending at num - difference (or 1 if none exists). Track the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

func longestSubsequence(arr []int, difference int) int {
	dp := make(map[int]int)
	ans := 0
	for _, num := range arr {
		dp[num] = dp[num-difference] + 1
		if dp[num] > ans {
			ans = dp[num]
		}
	}
	return ans
}
1
2
3
4
5
6
7
8
9

public int longestSubsequence(int[] arr, int difference) {
	Map<Integer, Integer> dp = new HashMap<>();
	int ans = 0;
	for (int num : arr) {
		dp.put(num, dp.getOrDefault(num - difference, 0) + 1);
		ans = Math.max(ans, dp.get(num));
	}
	return ans;
}
1
2
3
4
5
6
7
8
9

fun longestSubsequence(arr: IntArray, difference: Int): Int {
	val dp = mutableMapOf<Int, Int>()
	var ans = 0
	for (num in arr) {
		dp[num] = (dp[num - difference] ?: 0) + 1
		ans = maxOf(ans, dp[num]!!)
	}
	return ans
}
1
2
3
4
5
6
7
8

class Solution:
	def longestSubsequence(self, arr: list[int], difference: int) -> int:
		dp = {}
		ans = 0
		for num in arr:
			dp[num] = dp.get(num - difference, 0) + 1
			ans = max(ans, dp[num])
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

use std::collections::HashMap;
impl Solution {
	pub fn longest_subsequence(arr: Vec<i32>, difference: i32) -> i32 {
		let mut dp = HashMap::new();
		let mut ans = 0;
		for &num in &arr {
			let len = dp.get(&(num - difference)).copied().unwrap_or(0) + 1;
			dp.insert(num, len);
			ans = ans.max(len);
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function longestSubsequence(arr: number[], difference: number): number {
	const dp = new Map<number, number>();
	let ans = 0;
	for (const num of arr) {
		const len = (dp.get(num - difference) ?? 0) + 1;
		dp.set(num, len);
		ans = Math.max(ans, len);
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of arr. Each element is processed once.
  • 🧺 Space complexity: O(n), for the hash map storing subsequence lengths.