Longest Arithmetic Subsequence of Given Difference

Medium
313.

Longest Arithmetic Subsequence of Given Difference

Longest Arithmetic Subsequence of Given Difference is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr that is an arithmetic sequence with that exact common difference.

A subsequence keeps the relative order of the remaining elements but need not be contiguous.

Example 1

Input
arr = [1,2,3,4], difference = 1
Output
4

Example 2

Input
arr = [1,3,5,7], difference = 1
Output
1
Explanation
No two elements differ by exactly 1.

Example 3

Input
arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output
4
Explanation
The subsequence [7,5,3,1].

Constraints

  • 1 <= arr.length <= 40
  • -1000 <= arr[i], difference <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} difference
 * @return {number}
 */
var longestSubsequence = function(arr, difference) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Arithmetic Subsequence of Given Difference Solution

Longest Arithmetic Subsequence of Given Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Arithmetic Subsequence of Given Difference is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

Problem statement

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr that is an arithmetic sequence with that exact common difference.

A subsequence keeps the relative order of the remaining elements but need not be contiguous.

Example 1

Input: arr = [1,2,3,4], difference = 1
Output: 4

Example 2

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: No two elements differ by exactly 1.

Example 3

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The subsequence [7,5,3,1].

Constraints

  • 1 <= arr.length <= 40
  • -1000 <= arr[i], difference <= 1000

Hints for Longest Arithmetic Subsequence of Given Difference

  1. Hint 1

    Any such subsequence is determined by its last element — you never need to look further back than one step.

  2. Hint 2

    Keep a map from value to the longest chain ending at that value.

  3. Hint 3

    Reading map[x - difference] while processing x extends the chain in O(1).

How to solve Longest Arithmetic Subsequence of Given Difference

A chain with fixed difference is determined by its last value, so keep a map from value to the longest chain ending there and extend from x - difference.

Approach

  1. For each x, set best[x] = best.get(x - difference, 0) + 1.
  2. Track the maximum.

Why it works

The element before x in any valid chain must be exactly x - difference, so the longest chain ending at x is one more than the longest ending at that predecessor seen so far.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Later copies of x overwrite best[x] with a value at least as large, which is what you want.
  • A difference of 0 works unchanged — chains of equal values.

Reference solution

Python

def longestSubsequence(arr, difference: int) -> int:
    best = {}
    answer = 0
    for x in arr:
        best[x] = best.get(x - difference, 0) + 1
        answer = max(answer, best[x])
    return answer

Java

public static int longestSubsequence(int[] arr, int difference) {
    Map<Integer, Integer> best = new HashMap<>();
    int answer = 0;
    for (int x : arr) {
        int len = best.getOrDefault(x - difference, 0) + 1;
        best.put(x, len);
        if (len > answer) answer = len;
    }
    return answer;
}

C++

int longestSubsequence(vector<int>& arr, int difference) {
    unordered_map<int, int> best;
    int answer = 0;
    for (int x : arr) {
        int len = 1;
        auto it = best.find(x - difference);
        if (it != best.end()) len = it->second + 1;
        best[x] = len;
        answer = max(answer, len);
    }
    return answer;
}

JavaScript

var longestSubsequence = function(arr, difference) {
    const best = new Map();
    let answer = 0;
    for (let i = 0; i < arr.length; i++) {
        const prev = best.get(arr[i] - difference) || 0;
        const len = prev + 1;
        best.set(arr[i], len);
        if (len > answer) answer = len;
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets