Arithmetic Slices II - Subsequence

Hard
1500.

Arithmetic Slices II - Subsequence

Arithmetic Slices II - Subsequence is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Microsoft interviews.

A sequence is arithmetic when it has at least three elements and every two neighbours differ by the same amount. [4,4,4], [7,10,13] and [3,-1,-5,-9] are arithmetic; [1,2,4] and [5,8] are not.

Given an integer array nums, count its arithmetic subsequences. A subsequence keeps the original order but may skip elements. Two subsequences are different when they use different sets of indices, even if they hold the same values.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

Input
nums = [2,4,6,8,10]
Output
7
Explanation
`[2,4,6]`, `[4,6,8]`, `[6,8,10]`, `[2,4,6,8]`, `[4,6,8,10]`, `[2,4,6,8,10]` and `[2,6,10]`.

Example 2

Input
nums = [5,5,5,5]
Output
5
Explanation
Any three of the four positions (4 ways) and all four together.

Example 3

Input
nums = [9,6,3,7,0]
Output
3
Explanation
`[9,6,3]`, `[6,3,0]` and `[9,6,3,0]` — the `7` never fits.

Constraints

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • the answer fits in a 32-bit signed integer
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Arithmetic Slices II - Subsequence — Problem & Solution

Arithmetic Slices II - Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Arithmetic Slices II - Subsequence is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

A sequence is arithmetic when it has at least three elements and every two neighbours differ by the same amount. [4,4,4], [7,10,13] and [3,-1,-5,-9] are arithmetic; [1,2,4] and [5,8] are not.

Given an integer array nums, count its arithmetic subsequences. A subsequence keeps the original order but may skip elements. Two subsequences are different when they use different sets of indices, even if they hold the same values.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: `[2,4,6]`, `[4,6,8]`, `[6,8,10]`, `[2,4,6,8]`, `[4,6,8,10]`, `[2,4,6,8,10]` and `[2,6,10]`.

Example 2

Input: nums = [5,5,5,5]
Output: 5
Explanation: Any three of the four positions (4 ways) and all four together.

Example 3

Input: nums = [9,6,3,7,0]
Output: 3
Explanation: `[9,6,3]`, `[6,3,0]` and `[9,6,3,0]` — the `7` never fits.

Constraints

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • the answer fits in a 32-bit signed integer

Hints for Arithmetic Slices II - Subsequence

  1. Hint 1

    Build subsequences left to right: an arithmetic subsequence ending at index i with common difference d extends one that ends at some j < i with the same d.

  2. Hint 2

    Also count the 'weak' ones of length 2. Every pair (j, i) starts one, and a real answer is exactly a weak subsequence that gets extended at least once.

  3. Hint 3

    For each index keep a map from difference to the number of weak subsequences ending there. For every j < i with d = nums[i] - nums[j]: add count[j][d] to the answer, then add count[j][d] + 1 to count[i][d].

How to solve Arithmetic Slices II - Subsequence

Track weak arithmetic subsequences — length two or more. Length-2 ones are easy to start (every pair is one), and a length-≥3 one is precisely a weak subsequence ending at j with difference d, extended by an element nums[i] with nums[i] - nums[j] = d.

Approach

  1. Give every index i a hash map count[i] from difference to the number of weak subsequences ending at i with that difference.
  2. For each i and each j < i, let d = nums[i] - nums[j] (in 64 bits).
  3. Every weak subsequence counted in count[j][d] extends to a subsequence of length ≥ 3 ending at i: add count[j][d] to the answer.
  4. Record the new weak subsequences ending at i: count[i][d] += count[j][d] + 1 (the extensions plus the pair (j, i) itself).
  5. Return the accumulated answer.

Why it works

Each arithmetic subsequence is identified by its last two indices (j, i) and its prefix ending at j. When the pair (j, i) is processed, count[j][d] already holds every weak subsequence ending at j with difference d (all of them end at indices below i), so each arithmetic subsequence is added to the answer exactly once — at the moment its last element is appended — and length-2 pairs never reach the answer because they are added to count[i] only.

Complexity

  • Time — O(n^2)
  • Space — O(n^2)

Pitfalls

  • Differences of values near ±2^31 overflow 32 bits — compute d in 64-bit arithmetic.
  • Add count[j][d] to the answer, not count[j][d] + 1: the bare pair has length 2.
  • Equal values are fine: d = 0 is a valid difference, and duplicates are different subsequences because their indices differ.

Reference solution

Python

from typing import List

def numberOfArithmeticSlices(nums: List[int]) -> int:
    n = len(nums)
    count = [dict() for _ in range(n)]
    total = 0
    for i in range(n):
        here = count[i]
        for j in range(i):
            d = nums[i] - nums[j]
            c = count[j].get(d, 0)
            total += c
            here[d] = here.get(d, 0) + c + 1
    return total

Java

public static int numberOfArithmeticSlices(int[] nums) {
    int n = nums.length;
    long total = 0;
    List<Map<Long, Long>> count = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        Map<Long, Long> here = new HashMap<>();
        count.add(here);
        for (int j = 0; j < i; j++) {
            long d = (long) nums[i] - nums[j];
            long c = count.get(j).getOrDefault(d, 0L);
            total += c;
            here.put(d, here.getOrDefault(d, 0L) + c + 1);
        }
    }
    return (int) total;
}

C++

int numberOfArithmeticSlices(vector<int>& nums) {
    int n = nums.size();
    long long total = 0;
    vector<unordered_map<long long, long long>> count(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            long long d = (long long)nums[i] - nums[j];
            auto it = count[j].find(d);
            long long c = it == count[j].end() ? 0 : it->second;
            total += c;
            count[i][d] += c + 1;
        }
    }
    return (int)total;
}

JavaScript

var numberOfArithmeticSlices = function(nums) {
    var n = nums.length, total = 0;
    var count = [];
    for (var i = 0; i < n; i++) {
        var here = new Map();
        count.push(here);
        for (var j = 0; j < i; j++) {
            var d = nums[i] - nums[j];
            var c = count[j].get(d) || 0;
            total += c;
            here.set(d, (here.get(d) || 0) + c + 1);
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets