Arithmetic Slices II - Subsequence - Practice Coding Problems

Arithmetic Slices II - Subsequence - Problem

Given an integer array nums, return the number of all the arithmetic subsequences of nums.

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.

For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The test cases are generated so that the answer fits in 32-bit integer.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,4,6,8]

› Output: 3

💡 Note: Three arithmetic subsequences: [2,4,6], [4,6,8], and [2,4,6,8]. All have difference of 2.

Example 2 — Single Element Repeated

$ Input: nums = [7,7,7,7]

› Output: 4

💡 Note: All subsequences of length ≥3 are arithmetic with difference 0: [7,7,7] appears in 4 different ways, plus [7,7,7,7].

Example 3 — No Valid Subsequences

$ Input: nums = [2,3,5]

› Output: 0

💡 Note: Only one subsequence of length 3: [2,3,5]. Differences are 1 and 2, so not arithmetic.

Constraints

1 ≤ nums.length ≤ 1000
-2³¹ ≤ nums[i] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [2,4,6,8] with elements at different positions

Find Patterns

Identify arithmetic subsequences with consistent differences

Count Result

Total count of valid arithmetic subsequences of length ≥ 3

Key Takeaway

🎯 Key Insight: Use DP to track sequences by their differences, extending existing patterns efficiently

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is to use dynamic programming to track arithmetic sequences ending at each position with each difference. For each new element, we extend existing sequences and count those with 3+ elements. The optimal approach uses a 2D DP structure with hashmaps, achieving O(n²) time and O(n²) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with HashMap	O(n²)	O(n²)	Use DP to track arithmetic sequences ending at each position with each difference
Brute Force - Generate All Subsequences	O(2ⁿ × n)	O(n)	Generate all possible subsequences and check if they are arithmetic

Dynamic Programming with HashMap — Algorithm Steps

For each element, create a map of differences to sequence counts
For each pair (i,j) where j > i, calculate difference
Extend sequences ending at i with the same difference
Add new 2-element sequences starting from this pair

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create DP table for each position and difference

Extend

For each pair, extend sequences with matching difference

Count

Add valid 3+ element sequences to result

Code -

solution.c — C

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

#define HASH_SIZE 10007

typedef struct HashNode {
    long long key;
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode* buckets[HASH_SIZE];
} HashMap;

int hash(long long key) {
    return (int)((key % HASH_SIZE + HASH_SIZE) % HASH_SIZE);
}

int get(HashMap* map, long long key) {
    int idx = hash(key);
    HashNode* node = map->buckets[idx];
    while (node) {
        if (node->key == key) return node->value;
        node = node->next;
    }
    return 0;
}

void put(HashMap* map, long long key, int value) {
    int idx = hash(key);
    HashNode* node = map->buckets[idx];
    while (node) {
        if (node->key == key) {
            node->value = value;
            return;
        }
        node = node->next;
    }
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = map->buckets[idx];
    map->buckets[idx] = newNode;
}

int solution(int* nums, int numsSize) {
    if (numsSize < 3) return 0;
    
    HashMap* dp = (HashMap*)calloc(numsSize, sizeof(HashMap));
    int result = 0;
    
    for (int j = 1; j < numsSize; j++) {
        for (int i = 0; i < j; i++) {
            long long diff = (long long)nums[j] - nums[i];
            
            int count = get(&dp[i], diff);
            result += count;
            
            int currentCount = get(&dp[j], diff);
            put(&dp[j], diff, currentCount + count + 1);
        }
    }
    
    free(dp);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops through all pairs of elements, each pair processed in O(1) time

⚠ Quadratic Growth

Space Complexity

O(n²)

HashMap for each position storing difference counts, worst case O(n) differences per position

⚠ Quadratic Space

67.5K Views

Medium Frequency

~35 min Avg. Time

1.9K 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 HashMap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler