Problem Description

You are given an integer array arr and an integer difference. Your task is to find the length of the longest subsequence in arr that forms an arithmetic sequence where the difference between any two adjacent elements in the subsequence equals difference.

A subsequence is a sequence that can be obtained from the original array by deleting some elements (or none) without changing the order of the remaining elements. The elements in the subsequence don't need to be consecutive in the original array.

For example, if arr = [1, 2, 3, 4] and difference = 1, the entire array forms an arithmetic subsequence with difference 1, so the answer would be 4. If arr = [1, 5, 7, 8, 5, 3, 4, 2, 1] and difference = -2, the longest arithmetic subsequence would be [7, 5, 3, 1] with length 4.

The solution uses dynamic programming with a hash table approach. For each element x in the array, it calculates the length of the longest arithmetic subsequence ending at x by looking up the length of the subsequence ending at x - difference and adding 1. The hash table f stores these lengths, where f[x] represents the length of the longest arithmetic subsequence ending with value x. The final answer is the maximum value among all lengths stored in the hash table.

Intuition

When we think about building an arithmetic subsequence, we need to make decisions about which elements to include. The key insight is that for any element x in the array, if we want to include it in an arithmetic subsequence with a given difference, the previous element in that subsequence must be x - difference.

This observation leads us to a dynamic programming approach. As we traverse the array from left to right, for each element x, we ask: "What's the longest arithmetic subsequence that ends with x?"

To answer this, we need to know if there's an arithmetic subsequence ending with x - difference that we can extend. If such a subsequence exists with length k, then by adding x to it, we create a subsequence of length k + 1. If no such subsequence exists, then x starts a new subsequence of length 1.

The beauty of this approach is that we don't need to track all possible subsequences explicitly. We only need to remember, for each value we've seen, the length of the longest arithmetic subsequence ending with that value. This is why a hash table is perfect - it allows us to quickly look up f[x - difference] to determine how to update f[x].

As we process each element, we're essentially building up all possible arithmetic subsequences simultaneously, keeping track of only the longest one ending at each value. The final answer is simply the maximum length among all these subsequences.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a dynamic programming approach using a hash table to efficiently track the longest arithmetic subsequence ending at each value.

Data Structure Used:

• A hash table f (implemented as defaultdict(int)) where the key is a value from the array and the value is the length of the longest arithmetic subsequence ending with that key.

Algorithm Steps:

1. Initialize the hash table: Create a defaultdict(int) which automatically returns 0 for non-existent keys. This handles the base case where an element starts a new subsequence.

2. Iterate through the array: Process each element x in arr sequentially from left to right.

3. Update the DP state: For each element x, compute the length of the longest arithmetic subsequence ending at x using the recurrence relation:

   f[x] = f[x - difference] + 1

   • If x - difference exists in our hash table, it means we can extend that subsequence by including x
   • If x - difference doesn't exist, f[x - difference] returns 0, so f[x] becomes 1 (starting a new subsequence)

4. Find the maximum: After processing all elements, return max(f.values()) which gives us the length of the longest arithmetic subsequence in the entire array.

Time Complexity: O(n) where n is the length of the array, as we process each element once and hash table operations are O(1) on average.

Space Complexity: O(n) in the worst case when all elements are unique, as we might store up to n entries in the hash table.

The elegance of this solution lies in its simplicity - by maintaining just the length of the best subsequence ending at each value, we avoid the complexity of tracking the actual subsequences themselves.

Example Walkthrough

Let's walk through a concrete example with arr = [1, 5, 7, 8, 5, 3, 4, 2, 1] and difference = -2.

We'll track how our hash table f evolves as we process each element:

Initial state: f = {} (empty hash table)

Step 1: Process x = 1

• Check f[1 - (-2)] = f[3] → not found, returns 0
• Update: f[1] = 0 + 1 = 1
• State: f = {1: 1}

Step 2: Process x = 5

• Check f[5 - (-2)] = f[7] → not found, returns 0
• Update: f[5] = 0 + 1 = 1
• State: f = {1: 1, 5: 1}

Step 3: Process x = 7

• Check f[7 - (-2)] = f[9] → not found, returns 0
• Update: f[7] = 0 + 1 = 1
• State: f = {1: 1, 5: 1, 7: 1}

Step 4: Process x = 8

• Check f[8 - (-2)] = f[10] → not found, returns 0
• Update: f[8] = 0 + 1 = 1
• State: f = {1: 1, 5: 1, 7: 1, 8: 1}

Step 5: Process x = 5 (second occurrence)

• Check f[5 - (-2)] = f[7] → found! Returns 1
• Update: f[5] = 1 + 1 = 2 (we can extend the subsequence ending at 7)
• State: f = {1: 1, 5: 2, 7: 1, 8: 1}
• This represents the subsequence [7, 5]

Step 6: Process x = 3

• Check f[3 - (-2)] = f[5] → found! Returns 2
• Update: f[3] = 2 + 1 = 3 (extending [7, 5] to [7, 5, 3])
• State: f = {1: 1, 5: 2, 7: 1, 8: 1, 3: 3}

Step 7: Process x = 4

• Check f[4 - (-2)] = f[6] → not found, returns 0
• Update: f[4] = 0 + 1 = 1
• State: f = {1: 1, 5: 2, 7: 1, 8: 1, 3: 3, 4: 1}

Step 8: Process x = 2

• Check f[2 - (-2)] = f[4] → found! Returns 1
• Update: f[2] = 1 + 1 = 2
• State: f = {1: 1, 5: 2, 7: 1, 8: 1, 3: 3, 4: 1, 2: 2}

Step 9: Process x = 1 (second occurrence)

• Check f[1 - (-2)] = f[3] → found! Returns 3
• Update: f[1] = 3 + 1 = 4 (extending [7, 5, 3] to [7, 5, 3, 1])
• Final state: f = {1: 4, 5: 2, 7: 1, 8: 1, 3: 3, 4: 1, 2: 2}

Result: max(f.values()) = 4

The longest arithmetic subsequence is [7, 5, 3, 1] with length 4, where each consecutive pair has a difference of -2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

• The algorithm iterates through the array arr exactly once with a single for loop
• For each element x in the array, it performs constant time operations:
  • Looking up f[x - difference] in the dictionary: O(1) average case
  • Updating f[x] in the dictionary: O(1) average case
• After the loop, max(f.values()) runs in O(n) time in the worst case when all elements form a valid subsequence
• Total time complexity: O(n) + O(n) = O(n), where n is the length of the array arr

Space Complexity: O(n)

• The dictionary f stores at most n key-value pairs (one for each unique element in the array)
• In the worst case, when all elements are distinct, the dictionary will contain n entries
• Therefore, the space complexity is O(n), where n is the length of the array arr

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Handling Duplicate Values Incorrectly

The Problem: A critical pitfall in this solution is how duplicate values are handled. When the same value appears multiple times in the array, the hash table will overwrite the previous entry, potentially leading to incorrect results.

Consider this example:

• arr = [1, 3, 5, 3, 7], difference = 2
• When we process the first 3, we get dp[3] = dp[1] + 1 = 2 (sequence: [1, 3])
• When we process 5, we get dp[5] = dp[3] + 1 = 3 (sequence: [1, 3, 5])
• When we process the second 3, we update dp[3] = dp[1] + 1 = 2 again
• When we process 7, we get dp[7] = dp[5] + 1 = 4 (correctly using [1, 3, 5, 7])

In this case, the algorithm works correctly because we process elements left to right, and the hash table always maintains the most recent occurrence's subsequence length. However, this behavior might not be immediately obvious and could cause confusion.

Why This Actually Works: The algorithm is correct because:

1. We process elements from left to right
2. For any arithmetic subsequence, we only care about extending from the most recent valid predecessor
3. Overwriting with a duplicate doesn't affect future calculations since we've already processed all elements that could have used the previous value

Pitfall 2: Integer Overflow in Different Languages

The Problem: When calculating num - difference, integer overflow could occur in languages with fixed integer sizes. For example:

• If num = -2^31 (minimum 32-bit integer) and difference = 1
• Then num - difference = -2^31 - 1 would cause underflow

Solution: In Python, this isn't an issue due to arbitrary precision integers, but when implementing in other languages:

# For languages with fixed integer sizes, consider bounds checking:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
    dp = defaultdict(int)
  
    for num in arr:
        # Check if num - difference would cause overflow/underflow
        prev = num - difference
        # In Python this check is unnecessary, but in C++/Java you might need:
        # if (difference > 0 && num < INT_MIN + difference) continue;
        # if (difference < 0 && num > INT_MAX + difference) continue;
      
        dp[num] = dp[prev] + 1
  
    return max(dp.values())

Pitfall 3: Empty Array Edge Case

The Problem: If the input array is empty, max(dp.values()) will raise a ValueError because you cannot take the max of an empty sequence.

Solution: Add a guard clause to handle empty arrays:

def longestSubsequence(self, arr: List[int], difference: int) -> int:
    if not arr:  # Handle empty array
        return 0
      
    dp = defaultdict(int)
  
    for num in arr:
        dp[num] = dp[num - difference] + 1
  
    return max(dp.values())

Pitfall 4: Misunderstanding the Problem Requirements

The Problem: Developers might mistakenly think they need to track the actual subsequence elements or that the subsequence elements must be consecutive in the original array. This could lead to overly complex solutions.

Clarification:

• We only need the length, not the actual subsequence
• Elements in the subsequence maintain their relative order but don't need to be consecutive in the original array
• The arithmetic property only applies to the subsequence, not the original array positions