1027. Longest Arithmetic Subsequence Solution

Q: Is Longest Arithmetic Subsequence easy or hard?

Longest Arithmetic Subsequence is generally rated Medium on LeetCode. The difficulty comes from recognizing the dynamic programming state based on index and difference rather than the elements themselves.

Q: How to solve Longest Arithmetic Subsequence in O(n)?

Solving this problem in O(n) time is not generally possible because every pair of elements can define a unique arithmetic difference. The best known approach checks all pairs using dynamic programming with hash maps, resulting in O(n^2) time complexity.

Q: Longest Arithmetic Subsequence Python or Java solution?

Both Python and Java implementations typically use an array of hash maps. For each pair (j, i), compute diff = nums[i] - nums[j], read the previous length from dp[j], and update dp[i][diff]. This builds the longest subsequence in O(n^2) time.

Q: What is the best approach for Longest Arithmetic Subsequence?

Dynamic Programming with a HashMap per index is the most practical approach. For each pair of indices (j, i), compute the difference and extend an existing subsequence ending at j using a hash lookup. This solution runs in O(n^2) time and O(n^2) space and avoids allocating large fixed DP tables.

Q: What data structure is used in Longest Arithmetic Subsequence?

The core data structure is a hash map combined with dynamic programming. Each index maintains a map from difference value to subsequence length, allowing constant-time extension of previously discovered arithmetic sequences.

Q: What is the time complexity of Longest Arithmetic Subsequence?

The optimal solution runs in O(n^2) time because every pair of indices in the array is examined once. Each step performs a constant-time hash lookup or DP update. Space complexity is O(n^2) in the worst case to store subsequence lengths for different differences.

Q: Is Longest Arithmetic Subsequence asked at Google, Amazon, or Meta?

Arithmetic subsequence and dynamic programming with difference tracking appear frequently in interviews at large tech companies such as Amazon, Google, and Meta. Variants of this problem test DP state design, hash map usage, and pairwise iteration patterns.

The 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).

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Approach overview

Problem Overview: Given an integer array nums, find the length of the longest subsequence where the difference between consecutive elements is constant. The subsequence does not need to be contiguous, but the order must remain the same.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct strategy tries every pair of indices as the first two elements of a potential arithmetic subsequence. Once the difference diff = nums[j] - nums[i] is fixed, scan the rest of the array and greedily extend the sequence whenever the next expected value appears. This approach repeatedly searches the array for the next valid element, which leads to a cubic runtime in the worst case. It demonstrates the core idea—fix a difference and extend the sequence—but becomes impractical for large inputs.

Approach 2: Dynamic Programming with 2D DP Array (O(n^2) time, O(n^2) space)

A better solution stores results for subproblems. Define dp[i][d] as the length of the longest arithmetic subsequence ending at index i with difference d. For every pair of indices j < i, compute diff = nums[i] - nums[j]. If a sequence ending at j with this difference already exists, extend it: dp[i][diff] = dp[j][diff] + 1. Otherwise start a new sequence of length 2. This dynamic programming transition builds longer subsequences as you iterate through the array. The method fits naturally into dynamic programming patterns but can consume significant memory if differences are stored in a dense structure.

Approach 3: Dynamic Programming with HashMap Optimization (O(n^2) time, O(n^2) space)

The most practical implementation replaces the dense DP table with a hash map for each index. Each dp[i] is a map where the key is the difference and the value is the subsequence length ending at i. For every pair (j, i), compute the difference and perform a constant‑time hash lookup: dp[i][diff] = dp[j].get(diff, 1) + 1. This avoids allocating a large fixed difference range and stores only the differences that actually appear. The algorithm still checks every pair of indices, giving O(n^2) time, but the memory usage becomes much more practical. This technique combines ideas from array iteration and hash table lookups.

Recommended for interviews: Interviewers expect the dynamic programming insight. Starting with the brute force explanation shows you understand the arithmetic subsequence definition, but the HashMap DP solution demonstrates algorithmic maturity. It keeps the optimal O(n^2) time while handling arbitrary differences efficiently, which is the approach most candidates implement during interviews.

Approach 1: Dynamic Programming with 2D DP Array

This approach involves using a 2D dynamic programming array to keep track of the lengths of arithmetic subsequences ending at different indices with various common differences. The outer loop iterates over end indices while the inner loop considers all pairs of start and end indices to update the subsequence lengths.

Python

def longestArithSeqLength(nums):
    if len(nums) <= 2:
        return len(nums)
    dp = [{} for _ in range(len(nums))]
    max_length = 2
    for i in range(len(nums)):
        for j in range(i):
            diff = nums[i] - nums[j]
            if diff in dp[j]:
                dp[i][diff] = dp[j][diff] + 1
            else:
                dp[i][diff] = 2
            max_length = max(max_length, dp[i][diff])
    return max_length

# Example usage
nums = [3, 6, 9, 12]
print(longestArithSeqLength(nums))

Java

import java.util.HashMap;
import java.util.Map;

public class LongestArithmeticSubsequence {
    public static int longestArithSeqLength(int[] nums) {
        if (nums.length <= 2) return nums.length;
        Map<Integer, Integer>[] dp = new HashMap[nums.length];
        int maxLength = 2;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);
                maxLength = Math.max(maxLength, dp[i].get(diff));
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {3, 6, 9, 12};
        System.out.println(longestArithSeqLength(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestArithSeqLength(vector<int>& nums) {
    if (nums.size() <= 2) return nums.size();
    vector<unordered_map<int, int>> dp(nums.size());
    int maxLength = 2;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            dp[i][diff] = dp[j].count(diff) > 0 ? dp[j][diff] + 1 : 2;
            maxLength = max(maxLength, dp[i][diff]);
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {3, 6, 9, 12};
    cout << longestArithSeqLength(nums) << endl;
    return 0;
}

JavaScript

function longestArithSeqLength(nums) {
    if (nums.length <= 2) return nums.length;
    let dp = Array.from({length: nums.length}, () => new Map());
    let maxLength = 2;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            let diff = nums[i] - nums[j];
            dp[i].set(diff, (dp[j].get(diff) || 1) + 1);
            maxLength = Math.max(maxLength, dp[i].get(diff));
        }
    }
    return maxLength;
}

// Example usage
const nums = [3, 6, 9, 12];
console.log(longestArithSeqLength(nums));

#include <stdio.h>
#include <string.h>

int longestArithSeqLength(int* nums, int numsSize) {
    if (numsSize <= 2) return numsSize;
    int dp[numsSize][1001]; // Adjust for [-500, 500] difference range
    memset(dp, 0, sizeof(dp));
    int maxLength = 2;
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j] + 500; // Shift to be positive
            dp[i][diff] = dp[j][diff] ? dp[j][diff] + 1 : 2;
            if (dp[i][diff] > maxLength) {
                maxLength = dp[i][diff];
            }
        }
    }
    return maxLength;
}

int main() {
    int nums[] = {3, 6, 9, 12};
    int result = longestArithSeqLength(nums, 4);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestArithSeqLength(int[] nums) {
        if (nums.Length <= 2) return nums.Length;
        var dp = new Dictionary<int, int>[nums.Length];
        int maxLength = 2;
        for (int i = 0; i < nums.Length; i++) {
            dp[i] = new Dictionary<int, int>();
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].ContainsKey(diff)) {
                    dp[i][diff] = dp[j][diff] + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = Math.Max(maxLength, dp[i][diff]);
            }
        }
        return maxLength;
    }

    public static void Main(string[] args) {
        int[] nums = {3, 6, 9, 12};
        var sol = new Solution();
        Console.WriteLine(sol.LongestArithSeqLength(nums));
    }
}

The Python implementation utilizes a list of dictionaries to manage the lengths of arithmetic subsequences for each index and their respective differences. For every element `nums[i]`, it examines all preceding elements `nums[j]`, calculates the difference, and attempts to extend existing sequences.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Try this approach in the editor

Approach 2: Dynamic Programming with HashMap Optimization

This approach uses a simplified dynamic programming technique with HashMaps and tracks differences and their counts for each number. By leveraging HashMap structures, we manage subsequence lengths more efficiently and avoid using unnecessary space for non-existent differences.

Python

def longestArithSeqLength(nums):
    if len(nums) <= 2:
        return len(nums)
    dp = [{} for _ in range(len(nums))]
    max_length = 2
    for i in range(len(nums)):
        for j in range(i):
            diff = nums[i] - nums[j]
            dp[i][diff] = dp[j].get(diff, 1) + 1
            max_length = max(max_length, dp[i][diff])
    return max_length

# Example usage
nums = [9, 4, 7, 2, 10]
print(longestArithSeqLength(nums))

Java

import java.util.HashMap;
import java.util.Map;

public class LongestArithmeticSubsequence {
    public static int longestArithSeqLength(int[] nums) {
        if (nums.length <= 2) return nums.length;
        Map<Integer, Integer>[] dp = new HashMap[nums.length];
        int maxLength = 2;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);
                maxLength = Math.max(maxLength, dp[i].get(diff));
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {9, 4, 7, 2, 10};
        System.out.println(longestArithSeqLength(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestArithSeqLength(vector<int>& nums) {
    if (nums.size() <= 2) return nums.size();
    vector<unordered_map<int, int>> dp(nums.size());
    int maxLength = 2;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            dp[i][diff] = (dp[j].count(diff) ? dp[j][diff] : 1) + 1;
            maxLength = max(maxLength, dp[i][diff]);
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {9, 4, 7, 2, 10};
    cout << longestArithSeqLength(nums) << endl;
    return 0;
}

JavaScript

function longestArithSeqLength(nums) {
    if (nums.length <= 2) return nums.length;
    let dp = Array.from({ length: nums.length }, () => new Map());
    let maxLength = 2;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            let diff = nums[i] - nums[j];
            dp[i].set(diff, (dp[j].get(diff) || 1) + 1);
            maxLength = Math.max(maxLength, dp[i].get(diff));
        }
    }
    return maxLength;
}

// Example usage
const nums = [9, 4, 7, 2, 10];
console.log(longestArithSeqLength(nums));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define HASH_MAP_INIT_CAPACITY 16

typedef struct HashMap {
    int *keys;
    int *values;
    int capacity;
    int size;
} HashMap;

HashMap* createHashMap() {
    HashMap *map = (HashMap*) malloc(sizeof(HashMap));
    map->keys = (int*) malloc(sizeof(int) * HASH_MAP_INIT_CAPACITY);
    map->values = (int*) malloc(sizeof(int) * HASH_MAP_INIT_CAPACITY);
    map->capacity = HASH_MAP_INIT_CAPACITY;
    map->size = 0;
    return map;
}

int hashMapGet(HashMap *map, int key) {
    for (int i = 0; i < map->size; i++) {
        if (map->keys[i] == key) return map->values[i];
    }
    return 1; // Default value if not found
}

void hashMapPut(HashMap *map, int key, int value) {
    for (int i = 0; i < map->size; i++) {
        if (map->keys[i] == key) {
            map->values[i] = value;
            return;
        }
    }
    if (map->size == map->capacity) {
        map->capacity *= 2;
        map->keys = (int*) realloc(map->keys, sizeof(int) * map->capacity);
        map->values = (int*) realloc(map->values, sizeof(int) * map->capacity);
    }
    map->keys[map->size] = key;
    map->values[map->size] = value;
    map->size++;
}

int longestArithSeqLength(int* nums, int numsSize) {
    if (numsSize <= 2) return numsSize;
    HashMap* dp[numsSize];
    for (int i = 0; i < numsSize; i++) {
        dp[i] = createHashMap();
    }
    int maxLength = 2;
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            int length = hashMapGet(dp[j], diff) + 1;
            hashMapPut(dp[i], diff, length);
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    for (int i = 0; i < numsSize; i++) {
        free(dp[i]->keys);
        free(dp[i]->values);
        free(dp[i]);
    }
    return maxLength;
}

int main() {
    int nums[] = {9, 4, 7, 2, 10};
    printf("%d\n", longestArithSeqLength(nums, 5));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestArithSeqLength(int[] nums) {
        if (nums.Length <= 2) return nums.Length;
        var dp = new Dictionary<int, int>[nums.Length];
        int maxLength = 2;
        for (int i = 0; i < nums.Length; i++) {
            dp[i] = new Dictionary<int, int>();
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].ContainsKey(diff)) {
                    dp[i][diff] = dp[j][diff] + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = Math.Max(maxLength, dp[i][diff]);
            }
        }
        return maxLength;
    }

    public static void Main() {
        int[] nums = {9, 4, 7, 2, 10};
        var sol = new Solution();
        Console.WriteLine(sol.LongestArithSeqLength(nums));
    }
}

In Python, we utilize dictionaries for compactness and flexibility, addressing only meaningful key-difference pairs at each step to maintain the subsequence lengths efficiently.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2) worst case, but generally less due to the selective nature of storage.

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] as the maximum length of the arithmetic sequence ending with nums[i] and having a common difference of j. Initially, f[i][j]=1, that is, each element itself is an arithmetic sequence of length 1.

Since the common difference may be negative, and the maximum difference is 500, we can uniformly add 500 to the common difference, so the range of the common difference becomes [0, 1000].

Considering f[i], we can enumerate the previous element nums[k] of nums[i], then the common difference j=nums[i]-nums[k]+500, at this time f[i][j]=max(f[i][j], f[k][j]+1), then we update the answer ans=max(ans, f[i][j]).

Finally, return the answer.

If initially f[i][j]=0, then we need to add 1 to the answer when returning the answer.

The time complexity is O(n times (d + n)), and the space complexity is O(n times d). Where n and d are the length of the array nums and the difference between the maximum and minimum values in the array nums, respectively.

TypeScript

function longestArithSeqLength(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    const f: number[][] = Array.from({ length: n }, () => new Array(1001).fill(0));
    for (let i = 1; i < n; ++i) {
        for (let k = 0; k < i; ++k) {
            const j = nums[i] - nums[k] + 500;
            f[i][j] = Math.max(f[i][j], f[k][j] + 1);
            ans = Math.max(ans, f[i][j]);
        }
    }
    return ans + 1;
}

func longestArithSeqLength(nums []int) int {
	n := len(nums)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, 1001)
	}
	ans := 0
	for i := 1; i < n; i++ {
		for k := 0; k < i; k++ {
			j := nums[i] - nums[k] + 500
			f[i][j] = max(f[i][j], f[k][j]+1)
			ans = max(ans, f[i][j])
		}
	}
	return ans + 1
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with 2D DP Array	Time Complexity: O(n^2) Space Complexity: O(n^2)
Dynamic Programming with HashMap Optimization	Time Complexity: O(n^2) Space Complexity: O(n^2) worst case, but generally less due to the selective nature of storage.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Enumeration	O(n^3)	O(1)	Conceptual baseline to understand how arithmetic subsequences are formed
Dynamic Programming with 2D DP Array	O(n^2)	O(n^2)	When implementing a straightforward DP table and difference range is manageable
Dynamic Programming with HashMap Optimization	O(n^2)	O(n^2)	Preferred solution for interviews and real implementations with large difference ranges

Frequently asked questions

Is Longest Arithmetic Subsequence easy or hard?

Longest Arithmetic Subsequence is generally rated Medium on LeetCode. The difficulty comes from recognizing the dynamic programming state based on index and difference rather than the elements themselves.

How to solve Longest Arithmetic Subsequence in O(n)?

Solving this problem in O(n) time is not generally possible because every pair of elements can define a unique arithmetic difference. The best known approach checks all pairs using dynamic programming with hash maps, resulting in O(n^2) time complexity.

Longest Arithmetic Subsequence Python or Java solution?

Both Python and Java implementations typically use an array of hash maps. For each pair (j, i), compute diff = nums[i] - nums[j], read the previous length from dp[j], and update dp[i][diff]. This builds the longest subsequence in O(n^2) time.

What is the best approach for Longest Arithmetic Subsequence?

Dynamic Programming with a HashMap per index is the most practical approach. For each pair of indices (j, i), compute the difference and extend an existing subsequence ending at j using a hash lookup. This solution runs in O(n^2) time and O(n^2) space and avoids allocating large fixed DP tables.

What data structure is used in Longest Arithmetic Subsequence?

The core data structure is a hash map combined with dynamic programming. Each index maintains a map from difference value to subsequence length, allowing constant-time extension of previously discovered arithmetic sequences.

What is the time complexity of Longest Arithmetic Subsequence?

The optimal solution runs in O(n^2) time because every pair of indices in the array is examined once. Each step performs a constant-time hash lookup or DP update. Space complexity is O(n^2) in the worst case to store subsequence lengths for different differences.

Is Longest Arithmetic Subsequence asked at Google, Amazon, or Meta?

Arithmetic subsequence and dynamic programming with difference tracking appear frequently in interviews at large tech companies such as Amazon, Google, and Meta. Variants of this problem test DP state design, hash map usage, and pairwise iteration patterns.

Longest Arithmetic Subsequence solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with 2D DP Array

Approach 2: Dynamic Programming with HashMap Optimization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Arithmetic Subsequence solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with 2D DP Array

Approach 2: Dynamic Programming with HashMap Optimization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems