#1218

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Arithmetic Subsequence of Given Difference

Find the longest arithmetic subsequence with a given difference using dynamic programming and hash tables.

Problem Statement

Given an integer array arr and an integer difference, your task is to find the length of the longest subsequence in arr where the difference between any two adjacent elements in the subsequence is equal to the provided 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. For example, in the array [1, 2, 3, 4] with a difference of 1, the longest arithmetic subsequence is [1, 2, 3, 4], which has a length of 4.

Examples

Example 1

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

Output: 4

The longest arithmetic subsequence is [1,2,3,4].

Example 2

Input: arr = [1,3,5,7], difference = 1

Output: 1

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

The longest arithmetic subsequence is [7,5,3,1].

Constraints

1 <= arr.length <= 105
-104 <= arr[i], difference <= 104

Solution Approach

Use Dynamic Programming with Hash Tables

Use a dynamic programming approach to store the lengths of the arithmetic subsequences at each array element. A hash table is employed to store the subsequences' lengths, using the element's value as the key and its subsequence length as the value. This allows quick updates as you scan the array.

Scan Through Array Elements

Iterate through the array while checking if the previous element that can form an arithmetic subsequence exists in the hash table. If so, update the current subsequence length based on the previous element's subsequence length. This ensures that we build subsequences by maintaining the specified difference.

Track Maximum Length

As you iterate through the array, continuously update and track the maximum subsequence length found. The final answer is the length of the longest subsequence that maintains the required difference between adjacent elements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the array size n, as we scan each element once and perform hash lookups. The space complexity is also O(n) due to the hash table storing the lengths of subsequences for each element in the array. Overall, the solution is efficient with respect to both time and space.

What Interviewers Usually Probe

The candidate should demonstrate familiarity with dynamic programming techniques.
They should understand how hash tables are used to optimize subsequence tracking.
The candidate must ensure they can explain the trade-offs between time and space complexity in this approach.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for negative differences when scanning the array.
Overcomplicating the problem by trying to brute force through all possible subsequences.
Not using hash tables efficiently, leading to unnecessary recomputation or slower performance.

Follow-up variants

Consider variations where the difference is zero, which means the subsequence would consist of identical elements.
Explore scenarios where elements of the array are all unique but can form an arithmetic subsequence with a given difference.
Test with arrays that have negative and positive numbers mixed, making sure the algorithm handles both directions of differences.

FAQ

What is the approach for solving the Longest Arithmetic Subsequence of Given Difference problem?

The approach combines dynamic programming and hash tables to track subsequence lengths while scanning the array. The hash table stores the length of each subsequence ending at a specific value.

How do hash tables optimize the solution for the Longest Arithmetic Subsequence of Given Difference?

Hash tables allow for constant-time lookups, enabling quick access to the length of previous subsequences that can extend with the current element. This reduces the time complexity compared to brute-force approaches.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the input array. Each element is processed once, and hash lookups and insertions are O(1).

How does the space complexity of the solution scale?

The space complexity is O(n) because we store the length of subsequences for each element in a hash table, which requires linear space.

Can the solution handle negative differences in the Longest Arithmetic Subsequence of Given Difference?

Yes, the solution can handle negative differences by tracking subsequences where elements decrease by the given negative difference.

terminal

Solution

Solution 1: Dynamic Programming

We can use a hash table $f$ to store the length of the longest arithmetic subsequence ending with $x$.

1

2

3

4

5

6

class Solution:
    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())

Continue Practicing

#1048 longest string chain #1027 longest arithmetic subsequence #996 number of squareful arrays