Longest Arithmetic Subsequence

Problem

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Examples

Example 1:

1
2
3
4
5


Input:
nums = [3,6,9,12]
Output:
 4
**Explanation: ** The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

1
2
3
4
5


Input:
nums = [9,4,7,2,10]
Output:
 3
**Explanation: ** The longest arithmetic subsequence is [4,7,10].

Example 3:

1
2
3
4
5


Input:
nums = [20,1,15,3,10,5,8]
Output:
 4
**Explanation: ** The longest arithmetic subsequence is [20,15,10,5].

Solution

Method 1 – Dynamic Programming with Hash Map

Intuition

For each pair of indices, we can extend an arithmetic subsequence by checking the difference and updating the length for that difference. Using a hash map for each index allows us to efficiently track all possible differences.

Approach

For each index i, keep a map from difference d to the length of the longest arithmetic subsequence ending at i with difference d.
For each previous index j < i, update the map for i using the value from j.
Track the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<unordered_map<int, int>> dp(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int d = nums[i] - nums[j];
                dp[i][d] = max(dp[i][d], dp[j].count(d) ? dp[j][d] + 1 : 2);
                ans = max(ans, dp[i][d]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func longestArithSeqLength(nums []int) int {
    n, ans := len(nums), 0
    dp := make([]map[int]int, n)
    for i := range dp { dp[i] = map[int]int{} }
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            d := nums[i] - nums[j]
            v := 2
            if dp[j][d] > 0 { v = dp[j][d] + 1 }
            if v > dp[i][d] { dp[i][d] = v }
            if v > ans { ans = v }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length, ans = 0;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; ++i) dp[i] = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int d = nums[i] - nums[j];
                int v = dp[j].getOrDefault(d, 1) + 1;
                dp[i].put(d, Math.max(dp[i].getOrDefault(d, 0), v));
                ans = Math.max(ans, dp[i].get(d));
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    fun longestArithSeqLength(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        val dp = Array(n) { mutableMapOf<Int, Int>() }
        for (i in 0 until n) {
            for (j in 0 until i) {
                val d = nums[i] - nums[j]
                val v = dp[j].getOrDefault(d, 1) + 1
                dp[i][d] = maxOf(dp[i].getOrDefault(d, 0), v)
                ans = maxOf(ans, dp[i][d]!!)
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        n, ans = len(nums), 0
        dp = [{} for _ in range(n)]
        for i in range(n):
            for j in range(i):
                d = nums[i] - nums[j]
                v = dp[j].get(d, 1) + 1
                dp[i][d] = max(dp[i].get(d, 0), v)
                ans = max(ans, dp[i][d])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


impl Solution {
    pub fn longest_arith_seq_length(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        let mut dp = vec![std::collections::HashMap::new(); n];
        for i in 0..n {
            for j in 0..i {
                let d = nums[i] - nums[j];
                let v = *dp[j].get(&d).unwrap_or(&1) + 1;
                let entry = dp[i].entry(d).or_insert(0);
                *entry = (*entry).max(v);
                ans = ans.max(*entry);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    longestArithSeqLength(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        const dp: Record<number, number>[] = Array.from({length: n}, () => ({}));
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < i; j++) {
                const d = nums[i] - nums[j];
                const v = (dp[j][d] ?? 1) + 1;
                dp[i][d] = Math.max(dp[i][d] ?? 0, v);
                ans = Math.max(ans, dp[i][d]);
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^2) where n is the length of the array. Each pair is checked.
🧺 Space complexity: O(n^2) for the DP hash maps.

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming with Hash Map#

Intuition#

Approach#

Code#

Complexity#