Longest Arithmetic Subsequence of Given Difference

Longest Arithmetic Subsequence of Given Difference - Problem

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Complete Sequence

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

› Output: 4

💡 Note: The entire array forms an arithmetic sequence: 1→3→5→7, where each difference is 2. Length = 4.

Example 2 — Partial Sequence

$ Input: arr = [1,2,3,4], difference = 1

› Output: 4

💡 Note: The entire array forms an arithmetic sequence: 1→2→3→4, where each difference is 1. Length = 4.

Example 3 — Multiple Chains

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

› Output: 4

💡 Note: The longest arithmetic sequence with difference -2 is: 7→5→3→1. Length = 4.

Constraints

1 ≤ arr.length ≤ 10⁵
-10⁴ ≤ arr[i], difference ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,5,7] with difference = 2

Process

Find arithmetic subsequences with difference 2

Output

Return length 4 (entire array forms valid sequence)

Key Takeaway

🎯 Key Insight: Use hash map to track sequence lengths ending at each number for O(n) solution

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is that each number can extend the arithmetic sequence ending at (number - difference). Using a hash map to track sequence lengths gives us O(n) time complexity with optimal dynamic programming approach. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check which ones form arithmetic sequences
Dynamic Programming with Hash Map	O(n)	O(n)	Use hash map to store the length of arithmetic sequence ending at each number

Brute Force - Check All Subsequences — Algorithm Steps

Generate all possible subsequences
For each subsequence, check if it's arithmetic with given difference
Track the maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n possible subsequences

Validate

Check if each forms arithmetic sequence

Track Max

Keep the longest valid sequence length

Code -

solution.c — C

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

int generateSubsequences(int* arr, int arrSize, int difference, int index, int* current, int currentSize) {
    if (index == arrSize) {
        if (currentSize <= 1) return currentSize;
        // Check if it's arithmetic with given difference
        for (int i = 1; i < currentSize; i++) {
            if (current[i] - current[i-1] != difference) {
                return 0;
            }
        }
        return currentSize;
    }
    
    // Don't include current element
    int maxLen = generateSubsequences(arr, arrSize, difference, index + 1, current, currentSize);
    
    // Include current element
    current[currentSize] = arr[index];
    int withCurrent = generateSubsequences(arr, arrSize, difference, index + 1, current, currentSize + 1);
    if (withCurrent > maxLen) maxLen = withCurrent;
    
    return maxLen;
}

int solution(int* arr, int arrSize, int difference) {
    int* current = (int*)malloc(arrSize * sizeof(int));
    int result = generateSubsequences(arr, arrSize, difference, 0, current, 0);
    free(current);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int difference;
    scanf("%d", &difference);
    
    int result = solution(arr, arrSize, difference);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n possible subsequences, each taking O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and temporary subsequence storage

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

845 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

Brute Force - Check All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler