Arithmetic Slices II - Subsequence

hard dp hash map

Problem

Return the number of subsequences (length ≥ 3) of nums that form an arithmetic progression.

Inputnums = [2,4,6,8,10]

Output7

Three of length 3: (2,4,6), (4,6,8), (6,8,10), (2,6,10); plus longer ones.

nums

def number_of_arithmetic_slices(nums):
    n = len(nums)
    dp = [{} for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(i):
            d = nums[i] - nums[j]
            pre = dp[j].get(d, 0)
            dp[i][d] = dp[i].get(d, 0) + pre + 1
            count += pre
    return count

function numberOfArithmeticSlices(nums) {
  const n = nums.length;
  const dp = Array.from({length: n}, () => new Map());
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      const d = nums[i] - nums[j];
      const pre = dp[j].get(d) || 0;
      dp[i].set(d, (dp[i].get(d) || 0) + pre + 1);
      count += pre;
    }
  }
  return count;
}

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length, count = 0;
        Map[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                long d = (long) nums[i] - nums[j];
                int pre = dp[j].getOrDefault(d, 0);
                dp[i].merge(d, pre + 1, Integer::sum);
                count += pre;
            }
        }
        return count;
    }
}

int numberOfArithmeticSlices(vector& nums) {
    int n = nums.size(), count = 0;
    vector> dp(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            long d = (long) nums[i] - nums[j];
            int pre = dp[j].count(d) ? dp[j][d] : 0;
            dp[i][d] += pre + 1;
            count += pre;
        }
    }
    return count;
}

Explanation

We count arithmetic subsequences (pick any indices in order, not necessarily adjacent) of length at least 3. The trick is to count them by their last element and their common difference.

For each index i we keep a map dp[i] where dp[i][d] is the number of arithmetic subsequences that end at i and have common difference d — including "weak" pairs of length 2.

For every earlier index j, the difference is d = nums[i] - nums[j]. Any subsequence ending at j with that same d (there are pre = dp[j][d] of them, each already length ≥ 2) can be extended to i, producing a real answer of length ≥ 3 — so we add pre to count.

We also record the new sequences ending at i: the pre extended ones plus the brand-new length-2 pair (j, i), hence dp[i][d] += pre + 1. The +1 is the weak pair, which never counts toward the answer but seeds longer chains later.

Example: nums = [2,4,6,8,10]. Pairs all share d = 2, and the weak counts build up so each new element extends earlier chains, totaling 7 valid subsequences.

Time: O(n²) Space: O(n²)