LeetCode 1218 - Longest Arithmetic Subsequence of Given Difference

The problem asks for the length of the longest arithmetic subsequence in a given array arr such that the difference between consecutive elements equals a specified integer difference. A subsequence can skip elements but must preserve the original order.

leetcodemediumarrayhash-tabledynamic-programming

LeetCode Problem 1218

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming

Solution

Problem Understanding

The problem asks for the length of the longest arithmetic subsequence in a given array arr such that the difference between consecutive elements equals a specified integer difference. A subsequence can skip elements but must preserve the original order.

In other words, for each element arr[i] in the array, we want to know how long a sequence ending at that element can be if each element differs from the previous by exactly difference. The expected output is the maximum length among all such sequences.

The input array arr can have up to 10^5 elements and each element can range from -10^4 to 10^4, with difference also in the same range. This indicates that any brute-force solution exploring all subsequences explicitly will be too slow. Edge cases to consider include arrays where all elements are the same, arrays with no valid arithmetic subsequence longer than one element, and negative differences.

Approaches

The brute-force approach would involve generating all possible subsequences of arr and checking each one to see if it forms an arithmetic sequence with the given difference. While this is correct in principle, it is extremely inefficient because the number of subsequences grows exponentially with the length of arr. Specifically, generating all subsequences of an array of size n takes O(2^n) time, which is infeasible for n = 10^5.

The key insight for an optimal solution is that we do not need to generate all subsequences. Instead, we can use a hash map to track the length of the longest arithmetic subsequence ending at each value. If arr[i] - difference exists in the hash map, we can extend that subsequence by including arr[i]. This approach leverages dynamic programming using a hash table, achieving linear time complexity because we only process each element once.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generate all subsequences and check differences
Optimal O(n) O(n) Use hash map to track subsequence lengths dynamically

Algorithm Walkthrough

  1. Initialize an empty hash map dp where dp[value] stores the length of the longest arithmetic subsequence ending with value.
  2. Initialize a variable max_len to zero to track the overall longest subsequence found.
  3. Iterate through each element num in the array arr.
  4. For each num, check if num - difference exists in dp. If it does, it means we can extend the subsequence ending at num - difference by including num. Otherwise, start a new subsequence with length 1.
  5. Update dp[num] with the new length, either starting from 1 or extending the previous subsequence.
  6. Update max_len if dp[num] is greater than the current max_len.
  7. After processing all elements, max_len contains the length of the longest arithmetic subsequence.

Why it works: The hash map ensures that for every number we know the maximum length of a valid subsequence ending with that number. By always extending sequences from num - difference if it exists, we are effectively constructing the longest possible subsequence dynamically.

Python Solution

from typing import List

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        max_len = 0
        
        for num in arr:
            dp[num] = dp.get(num - difference, 0) + 1
            max_len = max(max_len, dp[num])
        
        return max_len

The implementation initializes an empty dictionary dp to store the lengths of subsequences ending at each value. For each element in arr, it either extends a previous subsequence ending at num - difference or starts a new one. The max_len variable tracks the overall maximum length, which is returned at the end.

Go Solution

func longestSubsequence(arr []int, difference int) int {
    dp := make(map[int]int)
    maxLen := 0
    
    for _, num := range arr {
        dp[num] = dp[num-difference] + 1
        if dp[num] > maxLen {
            maxLen = dp[num]
        }
    }
    
    return maxLen
}

In Go, we use a map dp to track subsequence lengths. The key differences from Python are type declarations and the handling of map defaults: accessing a missing key in a Go map returns the zero value for the value type, which is perfect for this algorithm because a missing key naturally returns 0. We update maxLen similarly to Python.

Worked Examples

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

num dp max_len
1 {1:1} 1
2 {1:1, 2:2} 2
3 {1:1, 2:2, 3:3} 3
4 {1:1, 2:2, 3:3, 4:4} 4

Output: 4

Example 2: arr = [1,3,5,7], difference = 1

num dp max_len
1 {1:1} 1
3 {1:1, 3:1} 1
5 {1:1, 3:1, 5:1} 1
7 {1:1, 3:1, 5:1, 7:1} 1

Output: 1

Example 3: arr = [1,5,7,8,5,3,4,2,1], difference = -2

num dp max_len
1 {1:1} 1
5 {1:1, 5:1} 1
7 {1:1, 5:1, 7:1} 1
8 {1:1, 5:1, 7:1, 8:1} 1
5 {1:1, 5:2, 7:1, 8:1} 2
3 {1:1, 5:2, 7:1, 8:1, 3:3} 3
4 {1:1, 5:2, 7:1, 8:1, 3:3, 4:1} 3
2 {1:1, 5:2, 7:1, 8:1, 3:3, 4:1, 2:4} 4
1 {1:5, 5:2, 7:1, 8:1, 3:3, 4:1, 2:4} 5

Output: 4 (since the longest sequence is [7,5,3,1])

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once, with hash map lookups in O(1) average time.
Space O(n) The hash map stores a key for each unique number in arr.

The algorithm scales linearly with the size of the array, and memory usage is proportional to the number of unique elements.

Test Cases

# Provided examples
assert Solution().longestSubsequence([1,2,3,4], 1) == 4  # arithmetic sequence increasing by 1
assert Solution().longestSubsequence([1,3,5,7], 1) == 1  # no valid sequence longer than 1
assert Solution().longestSubsequence([1,5,7,8,5,3,4,2,1], -2) == 4  # sequence decreasing by 2

# Edge cases
assert Solution().longestSubsequence([1], 0) == 1  # single element array
assert Solution().longestSubsequence([1,1,1,1], 0) == 4  # all elements same, difference 0
assert Solution().longestSubsequence([1,2,4,8,16], 1) == 2  # no consecutive difference match
assert Solution().longestSubsequence([-1,-2,-3,-4], -1) == 4  # negative numbers increasing
assert Solution().longestSubsequence([10000,-10000,0,5000,-5000], 5000) == 3  # large numbers with difference
Test Why
[1,2,3,4], 1 Normal increasing arithmetic sequence
[1,3,5,7], 1 No valid sequence longer than 1
[1,5,7,8,5,3,4,2,1], -2 Decreasing difference, multiple subsequences
[1], 0 Minimum input size