Longest Arithmetic Subsequence of Given Difference solution and explanation
Google
9 more videos on this problem
Longest Arithmetic Subsequence of Given Difference | Recur + Memo | Optimal | META | Leetcode-1218codestorywithMIK · 32:28 · 6K views
Longest Arithmetic Subsequence of Given Difference II DP II Hash Maps II Leetcode 1218Aryan Mittal · 9:02 · 5K views
LeetCode 1218. Longest Arithmetic Subsequence of Given DifferenceHappy Coding · 18:05 · 2K views
1218 Longest Arithmetic Subsequence of Given DifferenceKelvin Chandra · 3:19 · 2K views
Longest Arithmetic Subsequence of Given Difference - Leetcode 1218 - PythonTechError · 8:37 · 1K views
LeetCode 1218 Longest Arithmetic Subsequence of Given DifferenceJeevan Kumar - Cracckify · 8:25 · 1K views
Daily Leetcode #1200: Jul 14, 2023 - 1218. Longest Arithmetic Subsequence of Given DifferenceProgramming Live with Larry · 5:02 · 443 views
Longest Arithmetic Subsequence of Given Difference - Leetcode 1218Algorithms Casts · 7:00 · 403 views
1218 || Longest Arithmetic Subsequence of Given Difference || C++ || Leetcode Daily ChallengeCodeFreaks · 9:54 · 266 views
Leetcode | 1218. Longest Arithmetic Subsequence of Given DifferenceParth Mathuria · 12:08 · 254 views
The 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.
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 <= 104
Approach overview
Problem Overview: You receive an integer array arr and a fixed integer difference. The goal is to find the length of the longest subsequence where the difference between consecutive elements is exactly difference. The subsequence does not need to be contiguous, but the order of elements must remain the same.
Approach 1: Dynamic Programming with HashMap (Time: O(n), Space: O(n))
The key observation: if a number x appears in the array, the previous value in a valid arithmetic subsequence must be x - difference. Maintain a hash map where dp[x] stores the length of the longest subsequence ending with value x. Iterate through the array once. For each value x, check if x - difference already exists in the map. If it does, extend that subsequence: dp[x] = dp[x - difference] + 1. Otherwise start a new subsequence with length 1. Update the map and track the maximum length. Hash lookups keep the operation constant time, giving a linear pass solution. This approach relies heavily on Hash Table lookups combined with Dynamic Programming state transitions.
Approach 2: Optimized Dynamic Programming with Direct Indexing (Time: O(n), Space: O(n))
If the value range of the array is reasonably bounded, the hash map can be replaced with a direct-index array. Instead of storing states in a map, use an array where the index represents the number itself (with offset if negatives exist). For each element x, compute x - difference and look up the stored subsequence length directly from the DP array. Then update the current index with the extended length. Direct indexing removes hash overhead and improves constant factors while keeping the same recurrence. This technique still follows the same Array-based dynamic programming idea but trades memory for faster access.
Recommended for interviews: The hash map dynamic programming solution is the expected answer. It demonstrates that you recognized the recurrence relationship between values and used a constant-time lookup structure. Mentioning the direct-index optimization shows deeper understanding of performance tradeoffs. Interviewers usually care most about identifying the DP state dp[x] and deriving the transition dp[x] = dp[x - difference] + 1.
Approach 1: Dynamic Programming with HashMap
This 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.
def longestSubsequence(arr, difference):
dp = {}
max_length = 0
for num in arr:
dp[num] = dp.get(num - difference, 0) + 1
max_length = max(max_length, dp[num])
return max_lengthimport java.util.HashMap;
public class Solution {
public int longestSubsequence(int[] arr, int difference) {
HashMap<Integer, Integer> dp = new HashMap<>();
int max_length = 0;
for (int num : arr) {
dp.put(num, dp.getOrDefault(num - difference, 0) + 1);
max_length = Math.max(max_length, dp.get(num));
}
return max_length;
}
}#include <vector>
#include <unordered_map>
using namespace std;
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int, int> dp;
int max_length = 0;
for (int num : arr) {
dp[num] = dp[num - difference] + 1;
max_length = max(max_length, dp[num]);
}
return max_length;
}function longestSubsequence(arr, difference) {
const dp = new Map();
let max_length = 0;
for (const num of arr) {
dp.set(num, (dp.get(num - difference) || 0) + 1);
max_length = Math.max(max_length, dp.get(num));
}
return max_length;
}#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 20001
int hash(int key) {
return (key + 10000) % TABLE_SIZE;
}
int longestSubsequence(int* arr, int arrSize, int difference) {
int* dp = (int*)calloc(TABLE_SIZE, sizeof(int));
int max_length = 0;
for (int i = 0; i < arrSize; ++i) {
int num = arr[i];
int key = hash(num);
int prev_key = hash(num - difference);
dp[key] = dp[prev_key] + 1;
if (dp[key] > max_length) {
max_length = dp[key];
}
}
free(dp);
return max_length;
}using System;
using System.Collections.Generic;
public class Solution {
public int LongestSubsequence(int[] arr, int difference) {
Dictionary<int, int> dp = new Dictionary<int, int>();
int max_length = 0;
foreach (int num in arr) {
if (!dp.ContainsKey(num)) dp[num] = 0;
dp[num] = dp.GetValueOrDefault(num - difference, 0) + 1;
max_length = Math.Max(max_length, dp[num]);
}
return max_length;
}
}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.
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.
Approach 2: Optimized Dynamic Programming with Direct Indexing
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.
def longestSubsequence(arr, difference):
offset = 10000
dp = [0] * 20001
max_length = 0
for num in arr:
idx = num + offset
prev_idx = num - difference + offset
dp[idx] = dp[prev_idx] + 1
max_length = max(max_length, dp[idx])
return max_lengthpublic class Solution {
public int longestSubsequence(int[] arr, int difference) {
int[] dp = new int[20001];
int offset = 10000;
int max_length = 0;
for (int num : arr) {
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = Math.max(max_length, dp[idx]);
}
return max_length;
}
}#include <vector>
#include <algorithm>
using namespace std;
int longestSubsequence(vector<int>& arr, int difference) {
int dp[20001] = {0};
int max_length = 0;
int offset = 10000;
for (int num : arr) {
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = max(max_length, dp[idx]);
}
return max_length;
}function longestSubsequence(arr, difference) {
const dp = new Array(20001).fill(0);
const offset = 10000;
let max_length = 0;
for (const num of arr) {
const idx = num + offset;
const prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = Math.max(max_length, dp[idx]);
}
return max_length;
}#include <stdio.h>
int longestSubsequence(int* arr, int arrSize, int difference) {
int dp[20001] = {0};
int max_length = 0;
int offset = 10000;
for (int i = 0; i < arrSize; ++i) {
int num = arr[i];
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
if (dp[idx] > max_length) {
max_length = dp[idx];
}
}
return max_length;
}using System;
public class Solution {
public int LongestSubsequence(int[] arr, int difference) {
int[] dp = new int[20001];
int offset = 10000;
int max_length = 0;
foreach (int num in arr) {
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = Math.Max(max_length, dp[idx]);
}
return max_length;
}
}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.
Time Complexity: O(n), where n is the length of arr.
Space Complexity: O(1) (constant size array mentioned in constraints).
Approach 3: Dynamic Programming
We can use a hash table f to store the length of the longest arithmetic subsequence ending with x.
Traverse the array arr, and for each element x, update f[x] to be f[x - difference] + 1.
After the traversal, return the maximum value in f as the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array arr.
function longestSubsequence(arr: number[], difference: number): number {
const f: Map<number, number> = new Map();
for (const x of arr) {
f.set(x, (f.get(x - difference) ?? 0) + 1);
}
return Math.max(...f.values());
}func longestSubsequence(arr []int, difference int) (ans int) {
f := map[int]int{}
for _, x := range arr {
f[x] = f[x-difference] + 1
ans = max(ans, f[x])
}
return
}use std::collections::HashMap;
impl Solution {
pub fn longest_subsequence(arr: Vec<i32>, difference: i32) -> i32 {
let mut f = HashMap::new();
let mut ans = 0;
for &x in &arr {
let count = f.get(&(x - difference)).unwrap_or(&0) + 1;
f.insert(x, count);
ans = ans.max(count);
}
ans
}
}Complexity comparison
| 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. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with HashMap | O(n) | O(n) | General case. Works for any integer range and is the most common interview solution. |
| Optimized DP with Direct Indexing | O(n) | O(n) | When value range is limited and you want faster constant-time lookups without hash overhead. |
Frequently asked questions
Is Longest Arithmetic Subsequence of Given Difference easy or hard?
The problem is rated Medium because recognizing the dynamic programming relationship is not immediately obvious. Once the recurrence dp[x] = dp[x - difference] + 1 is identified, the implementation becomes straightforward.
Longest Arithmetic Subsequence of Given Difference Python/Java solution
Python and Java implementations follow the same idea: iterate through the array and store dp[x] = dp.get(x - difference, 0) + 1. Python typically uses a dictionary, while Java uses a HashMap<Integer, Integer>. Both achieve O(n) time complexity.
How to solve Longest Arithmetic Subsequence of Given Difference in O(n)?
Use a hash map where the key is the value in the array and the value is the length of the longest subsequence ending with that number. For each element x, compute dp[x] = dp[x - difference] + 1 if the previous value exists; otherwise start a new subsequence of length 1. Track the maximum length during the iteration.
What is the best approach for Longest Arithmetic Subsequence of Given Difference?
Dynamic programming with a hash map is the most effective approach. Store the length of the longest subsequence ending at value x using dp[x]. For each number, check whether x - difference already exists and extend that subsequence. This produces an O(n) time and O(n) space solution.
Is Longest Arithmetic Subsequence of Given Difference asked at Google/Amazon/Meta?
Arithmetic subsequence and dynamic programming problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test understanding of hash maps, DP state transitions, and sequence pattern recognition.
What data structure is used in Longest Arithmetic Subsequence of Given Difference?
The main data structure is a hash map (dictionary) that stores dynamic programming states. Each key represents a value from the array and maps to the longest arithmetic subsequence ending with that value.
What is the time complexity of Longest Arithmetic Subsequence of Given Difference?
The optimal solution runs in O(n) time because each element is processed once with constant-time hash lookups. Space complexity is O(n) since the hash map stores subsequence lengths for encountered values.