Hard Problemscountingcombinatoricsgrid

Count of AP Subsequences

Given an array of integers, count the subsequences of length three or more whose elements form an arithmetic progression, meaning each chosen value after the first differs from the one before it by the same fixed amount.

Do this lesson first: climbing stairs

Example input

values = [2, 4, 6, 8]. Count arithmetic subsequences of length at least 3.

Expected output

3

Work through the example

Keep the original order, but allow skipped indices. An arithmetic subsequence has the same difference between every consecutive pair of chosen terms. The valid answers are [2, 4, 6], [4, 6, 8], and [2, 4, 6, 8], all with difference 2. A pair such as [2, 6] starts a possible progression but is too short to count. Different choices of indices count separately, even when their values are identical.

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

For every j < i: d = values[i] - values[j]; extend = dp[j][d] or 0; answer += extend; dp[i][d] += extend + 1.

Choose the previous index j before the new final index i. Every stored sequence ending at j with difference d can append values[i], so extend sequences now qualify for the answer. The extra 1 creates the new pair (j, i), which belongs in dp but not in answer. Every new sequence has a unique previous index j, so different transitions count disjoint choices of indices.

Start every endpoint map empty and answer at 0. A missing difference means 0 sequences, not an uncomputed state. Visit i from left to right, then every j from 0 to i - 1. Each dp[j] is complete before it is read. Inputs shorter than 3 return 0. Do not sort the input: subsequences must retain the original index order. JavaScript inputs must be safe integer Numbers; convert values to BigInt before subtraction so differences remain exact even when they exceed the safe Number range. Store counts and answer as BigInt too.

For [2, 4, 6, 8], index 0 has no pairs. At index 1 (value 4), (2, 4) sets dp[1][2] = 1 and adds nothing to answer. At index 2 (value 6), (2, 6) sets dp[2][4] = 1. Extending dp[1][2] = 1 adds [2, 4, 6] to answer, now 1; dp[2][2] = 1 + 1 = 2 stores [4, 6] and [2, 4, 6]. At index 3 (value 8), new pairs [2, 8] and [4, 8] set dp[3][6] = 1 and dp[3][4] = 1 without increasing answer. Extending the two sequences in dp[2][2] adds [4, 6, 8] and [2, 4, 6, 8], so answer becomes 3. dp[3][2] = 2 + 1 = 3 also includes the new pair [6, 8]. Return the accumulated answer 3, not the sum of endpoint maps, which also contain pairs.

Time O(n²) expected map operations across n(n - 1)/2 index pairs. BigInt arithmetic cost grows with the bit length of the values and counts.Space O(n²) map entries in the worst case, plus O(n) converted values. This entry count excludes the variable bit length of BigInt keys and counts.

The code, the trap, the variations

count-of-ap-subsequences.ts

1function countArithmeticSubsequences(values) {
2 if (values.some((value) => !Number.isSafeInteger(value))) {
3 throw new RangeError("Every value must be a safe integer.");
4 }
5 const integers = values.map((value) => BigInt(value));
6 const dp = integers.map(() => new Map());
7 let answer = BigInt(0);
8 for (let i = 0; i < integers.length; i++) {
9 for (let j = 0; j < i; j++) {
10 const difference = integers[i] - integers[j];
11 const extend = dp[j].get(difference) ?? BigInt(0);
12 answer += extend;
13 dp[i].set(difference, (dp[i].get(difference) ?? BigInt(0)) + extend + BigInt(1));
14 }
15 }
16 return answer;
17}

Where people go wrong

Do not add extend + 1 to answer: the extra 1 is only a pair. Do not use one shared map for every endpoint or replace accumulated counts with extend + 1; multiple previous indices may contribute to the same endpoint and difference. Zero and negative differences are valid. Preserve index order and count equal-valued choices separately. Number counts can silently lose precision; this implementation returns BigInt, so use answer.toString() for display and avoid converting a large result back to Number.

Count progressions of length at least 2.
Add extend + 1 to answer, since each new pair now qualifies.
Count progressions of exactly k terms.
Track length alongside endpoint and difference, extending length l - 1 into length l. The current map combines all lengths and cannot separate exactly k.
Find the longest arithmetic subsequence.
Store the best length per endpoint and difference, then combine with max instead of adding counts. A new pair has length 2.
Count contiguous arithmetic slices.
Require adjacent indices. Track the number of valid slices ending at each position by comparing consecutive differences; the arbitrary-index map is unnecessary.

Section 13

Count of AP Subsequences: extend a matching difference

Find every arithmetic subsequence of length at least 3 in [2, 4, 6, 8]. The answers are [2, 4, 6], [4, 6, 8], and [2, 4, 6, 8]. AP means arithmetic progression: consecutive chosen terms have equal differences. Chosen indices must increase, but they need not be adjacent.

Test your reasoning

Choose an answer for each question. You can try again after a hint.

0 / 2 answered correctly

1. dp[2][2] = 2 stores [4, 6] and [2, 4, 6]. When 8 is appended, what does this transition add to answer, and what count does it contribute to dp[3][2]?

2. How many arithmetic subsequences of length at least 3 does [5, 5, 5, 5] contain, counting different index choices separately?

Check your understanding

1. dp[2][2] = 2 stores [4, 6] and [2, 4, 6]. When 8 is appended, what does this transition add to answer, and what count does it contribute to dp[3][2]?

Answer +2; map +3
Answer +3; map +3
Answer +1; map +2
Answer +2; map +2

2. How many arithmetic subsequences of length at least 3 does [5, 5, 5, 5] contain, counting different index choices separately?

1
2
4
5

Flashcards: cover the answer to recall it

What does dp[i][d] count in arithmetic-subsequence counting?

Index-distinct arithmetic subsequences with at least 2 terms, ending exactly at index i with common difference d. Pairs are stored to seed later triples.

Why does a transition add extend to answer but extend + 1 to dp[i][d]?

The extend old sequences gain a term and now have at least 3 terms. The extra 1 starts the pair (j, i), which can be extended later but is not yet a qualifying answer.

Can the input be sorted or equal values deduplicated before counting?

No. Sorting changes the allowed index order, and deduplication removes distinct index choices. Keep all original positions, including repeated values; zero and negative differences are valid.

Quiz answer key

1. A. Add 2 to answer for [4, 6, 8] and [2, 4, 6, 8]. Contribute 2 + 1 = 3 to the map because [6, 8] must also be available for future extensions.

2. D. All four triples and the one quadruple have difference 0, giving 4 + 1 = 5. Identical values do not merge different choices of indices.

Review these notes and download the PDF

Min cost to sort strings using Reversals