Leetcode 446. Arithmetic Slices II - Subsequence

Problem Explanation

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. A subsequence slice of an array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N. A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2. We are given an array and we have to find the number of arithmetic subsequence slices in the array.

Example: Suppose we have an array [2, 4, 6, 8, 10]. The arithmetic subsequence slices in this array are: [2,4,6], [4,6,8], [6,8,10], [2,4,6,8], [4,6,8,10], [2,4,6,8,10], [2,6,10].

Note that [2,6,10] is also an arithmetic subsequence slice, because although it is not a contiguous subarray, it maintains a consistent difference of 4 between each element and the next. Hence, the output will be 7.

Solution Approach

We can solve this problem using dynamic programming and hash map. A key insight in this approach is that we need three indices to uniquely identify a subsequence: the last two indices of the subsequence and the common difference. The main idea of this solution is to keep track of the number of arithmetic subsequences ending at each index and with each difference.

Create a 2D dp array, where dp[i][j] indicates the number of subsequence slices ending at i with difference A[i] - A[j]. Also, create a map numToIndices where the key is a The value at numToIndices[A[i] - A[j]] will give us the dp[j][k] for all k < j.

Each element in the input array iterates over all previous elements and updates its state in the dp array. For each pair of indices i and j (i > j), we find the number of subsequences ending at an index less than j with a difference of A[i] - A[j]. This number is added to the total count of arithmetic subsequence slices.

Example: For example, for the input array [2, 4, 6, 8, 10], the dp array after examining each element in turn is:

After summing up all the values in the dp array, we get the number of arithmetic subsequence slices as 7.

Python Solution

1
2python
3class Solution:
4  def numberOfArithmeticSlices(self, nums):
5    n = len(nums)
6    ans = 0
7    dp = [{} for _ in range(n)] # To keep track of slices ending at each index with each difference
8
9    for i in range(n):
10        for j in range(i):
11            diff = nums[i] - nums[j] 
12            count = dp[j].get(diff, 0)
13            ans += count
14            dp[i][diff] = dp[i].get(diff, 0) + count + 1
15
16    return ans

Java Solution

1
2java
3import java.util.*;
4class Solution {
5  public int numberOfArithmeticSlices(int[] A) {
6    int res = 0;
7    Map<Integer, Integer>[] map = new Map[A.length];
8
9    for (int i = 0; i < A.length; i++) {
10      map[i] = new HashMap<>(i);
11
12      for (int j = 0; j < i; j++) {
13        long diff = (long)A[i] - A[j];
14        if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
15
16        int d = (int)diff;
17        int c1 = map[i].getOrDefault(d, 0);
18        int c2 = map[j].getOrDefault(d, 0);
19        res += c2;
20        map[i].put(d, c1 + c2 + 1);
21      }
22    }
23
24    return res;
25  }
26}

JavaScript Solution

1
2javascript
3var numberOfArithmeticSlices = function(A) {
4    let dp = Array.from({length: A.length}, () => new Map());
5    let count = 0;
6    
7    for (let i = 0; i < A.length; i++) {
8        for (let j = 0; j < i; j++) {
9            let diff = A[i] - A[j];
10            let ctJ = dp[j].get(diff) || 0;
11            let ctI = dp[i].get(diff) || 0;
12            dp[i].set(diff, ctI + ctJ + 1);
13            count += ctJ;
14        }
15    }
16    
17    return count;
18};

C++ Solution

1
2cpp
3#include<unordered_map>
4#include<vector>
5using namespace std;
6
7class Solution {
8public:
9  int numberOfArithmeticSlices(vector<int>& A) {
10    int res = 0;
11    vector<unordered_map<int, int>> cnt(A.size());
12    for (int i = 0; i < A.size(); i++)
13      for (int j = 0; j < i; j++) {
14        long diff = (long)A[i] - A[j];
15        if (diff < INT_MIN || diff > INT_MAX) continue;
16        int difference = (int)diff;
17        int sum = 0;
18        if (cnt[j].count(difference)) sum = cnt[j][difference];
19        res += sum;
20        cnt[i][difference] += sum + 1;
21      }
22    return res;
23  }
24};

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5public class Solution {
6  public int NumberOfArithmeticSlices(int[] A) {
7    int res = 0;
8    List<Dictionary<int, int>> map = new List<Dictionary<int, int>>();
9    for (int i = 0; i < A.Length; i++) {
10        map.Add(new Dictionary<int, int>(i));
11
12        for (int j = 0; j < i; j++) {
13            if ((long)A[i] - A[j] > int.MaxValue || (long)A[i] - A[j] < int.MinValue) continue;
14
15            int diff = A[i] - A[j];
16            int count1 = map[i].ContainsKey(diff) ? map[i][diff] : 0;
17            int count2 = map[j].ContainsKey(diff) ? map[j][diff] : 0;
18            res += count2;
19            map[i][diff] = count1 + count2 + 1;
20        }
21    }
22    return res;
23  }
24}

In all these solutions, we use a 2D dp array/hashmap to hold all possible differences for all possible start and end points within our array. We iterate through every pair of elements in the array and calculate their differences. By looking up this difference in the dp at the index of the second element, we can determine how many subsequences there are that end with this element and have this difference. This count is then added to a running total of subsequences. For each pair, we also add this count to the number of subsequences that end with the first element and have this difference, or we create a new entry in dp if it does not exist. This way, we continually expand our ability to find subsequences as we move through the array. The final result is then the total number of subsequences we have found.In terms of time complexity, these solutions are O(n^2), where n is the number of elements in the input array. This is because for each element in the array, we potentially have to iterate over all previous elements to calculate the difference and update the mapping of differences. The space complexity is also O(n^2), where n is the number of elements in the array. This is because in the worst case, we will need a unique entry in the dp array/hash map for each pair of elements in the array. However, each of these entries only requires O(1) space, so the total space complexity is still O(n^2). Conceptually, this is because we are storing a mapping of all possible differences for all possible pairs of start and end points in the array.

The key takeaway of this problem is the combination of dynamic programming and hashmap to keep track of the number of arithmetic subsequences ending at each index with each difference. This forms the core logic that enables the finding of all arithmetic subsequence slices in an array.

In problems similar with this one that involve finding specific patterns or arrangements within an array or collection of data, this technique can be useful. Dynamic programming allows us to store and re-use computations, reducing repetitive work and often drastically cutting down on runtime. Hashmaps enable quick look-ups and can be utilized to store mappings between items and their counts, as in this case.

To further practice and understand this technique, consider tasks that involve pattern-finding, particularly where dynamic programming can be utilized to store and re-use intermediate results. It is also useful to consider how a running total can be kept and updated as the program iterates through the data set. The efficiency of these solutions is heavily reliant on the efficient use of memory space for storing intermediate results and count mappings. Hence, it is also a good practice to have a solid understanding of memory management in programming.