Longest Arithmetic Subsequence - Practice Coding Problems

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

Input & Output

Example 1 — Basic Arithmetic Sequence

$ Input: nums = [3,6,9,12]

› Output: 4

💡 Note: The entire array forms an arithmetic subsequence with common difference 3: [3,6,9,12]. Length = 4.

Example 2 — Multiple Arithmetic Subsequences

$ Input: nums = [9,4,7,2,10]

› Output: 3

💡 Note: The longest arithmetic subsequences are [4,7,10] with difference 3, and [9,7,2] with difference -3. Both have length 3.

Example 3 — No Long Arithmetic Sequence

$ Input: nums = [20,1,15,3,10,5,8]

› Output: 4

💡 Note: The longest arithmetic subsequence is [20,15,10,5] with common difference -5. Length = 4.

Constraints

2 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with various numbers

Find Differences

Calculate differences between all pairs

Build Sequences

Extend arithmetic sequences with same difference

Key Takeaway

🎯 Key Insight: Use dynamic programming to track the longest arithmetic sequence ending at each position for every possible common difference

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to use dynamic programming where dp[i][diff] represents the length of the longest arithmetic subsequence ending at position i with common difference diff. For each position, we look at all previous positions and extend existing sequences. Best approach uses DP with hash maps: Time O(n²), Space O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Hash Maps	O(n²)	O(n²)	Use DP with hash maps to track longest sequence ending at each position
Space-Optimized DP	O(n²)	O(n × k)	Optimize space by using more efficient data structures and processing
Brute Force - Check All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check if they are arithmetic

Dynamic Programming with Hash Maps — Algorithm Steps

Initialize DP array with hash maps
For each pair (j,i), calculate difference and extend sequence
Update dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1)
Return maximum value across all positions and differences

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Create hash maps for each position

Calculate Differences

For each pair, find difference and extend sequence

Update Maximum

Track longest sequence across all differences

Code -

solution.c — C

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

#define MAX_N 1000
#define MAX_DIFF 20001
#define OFFSET 10000

int solution(int* nums, int n) {
    if (n <= 2) return n;
    
    // dp[i][diff + OFFSET] = length of longest arithmetic subsequence
    // ending at position i with common difference diff
    int dp[MAX_N][MAX_DIFF];
    memset(dp, 0, sizeof(dp));
    
    int maxLength = 2;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            if (diff < -OFFSET || diff >= OFFSET) continue;
            
            int diffIndex = diff + OFFSET;
            // If we have a sequence ending at j with this difference, extend it
            // Otherwise, start a new sequence of length 2
            dp[i][diffIndex] = dp[j][diffIndex] > 0 ? dp[j][diffIndex] + 1 : 2;
            if (dp[i][diffIndex] > maxLength) {
                maxLength = dp[i][diffIndex];
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[MAX_N];
    int n = 0;
    if (strlen(line) > 2) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            nums[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops through all pairs of positions

⚠ Quadratic Growth

Space Complexity

O(n²)

Hash map for each position storing different common differences

⚠ Quadratic Space

89.3K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Hash Maps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler