{x}
blog image

Longest Arithmetic Subsequence of Given Difference

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

Solution Explanation: Longest Arithmetic Subsequence of Given Difference

This problem asks us to find the length of the longest arithmetic subsequence within a given array arr, where the common difference between consecutive elements is a specified value difference.

Approach: Dynamic Programming with Hash Table

The most efficient approach is to use dynamic programming in conjunction with a hash table (or dictionary in Python). The hash table will store the length of the longest arithmetic subsequence ending at each number encountered so far.

Algorithm:

  1. Initialization: Create a hash table (e.g., f in the code examples) to store the lengths of arithmetic subsequences. Initially, it's empty or contains all entries with a value of 0.

  2. Iteration: Iterate through the input array arr. For each element x:

    • Check if x - difference exists as a key in the hash table.
    • If it exists, it means we've encountered a number that could be part of an arithmetic subsequence ending at x. The length of the subsequence ending at x will be one more than the length of the subsequence ending at x - difference (f[x - difference] + 1).
    • If x - difference doesn't exist, it implies x starts a new subsequence of length 1.
    • Update the hash table: f[x] = f[x - difference] + 1 (or f[x] = 1 if x - difference is not found).

  3. Finding the Maximum: After iterating through the entire array, the hash table f will contain the length of the longest arithmetic subsequence ending at each number. The maximum value in f represents the length of the overall longest arithmetic subsequence. Return this maximum value.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array arr. We iterate through the array once. Hash table lookups and insertions are considered O(1) on average.

  • Space Complexity: O(n) in the worst case. The hash table f might store up to n entries if all elements form part of a unique arithmetic subsequence. In some cases, it could use less space.

Code Examples (with detailed explanations)

The code examples provided in the problem statement demonstrate this algorithm in multiple languages. Let's highlight key aspects of one example (Python):

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        f = defaultdict(int)  # defaultdict ensures key existence without error handling
        for x in arr:
            f[x] = f[x - difference] + 1  # Crucial DP update step
        return max(f.values())  # Find the maximum length in the hash table

  • defaultdict(int): This ensures that if a key (x - difference) is not found in f, it automatically creates the key with a default value of 0, avoiding KeyError exceptions. This is a Python-specific optimization. Other languages might require explicit checking for key existence (using get methods or similar).

  • f[x] = f[x - difference] + 1: This line is the core of the dynamic programming solution. It updates the length of the subsequence ending at x based on the length of the subsequence ending at x - difference.

The other code examples (Java, C++, Go, TypeScript, Rust, Javascript) follow the same algorithmic approach but use the respective language's hash table/map implementations. The fundamental logic remains consistent across all languages.