446. Arithmetic Slices II - Subsequence

Arithmetic Slices II - Subsequence

Problem Description

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.

 

Example 1:

Input: nums = [2,4,6,8,10]
Output: 7

Explanation: All arithmetic subsequence slices 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]

Example 2:

Input: nums = [7,7,7,7,7]
Output: 16

Explanation: Any subsequence of this array is arithmetic.

 

Constraints:

• 1  <= nums.length <= 1000


• -231 <= nums[i] <= 231 - 1

Approach) Dynamic Programming

var numberOfArithmeticSlices = function (nums, dp = new Map(), result = 0) {
    nums.forEach((n, k) => {
        dp[k] = new Map();

        for (let i = 0; i < k; i++) {
            let m = nums[i];
            let diff = n - m;
            let apsAsK = dp[k].get(diff) || 0;
            let apsAsI = dp[i].get(diff) || 0;

			result += apsAsI;
            dp[k].set(diff, apsAsK + apsAsI + 1);
        }
    });

    return result;
};

Another Way) Dynamic Programming

dp[i] contains maps between common differences and the number of arithmetic subsequences that end with nums[i]. We take a look at all i < j and update dp[i] accordingly.

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
  let dp = new Array(nums.length);
  for(let i = 0; i < nums.length; i++) {
    dp[i] = new Map();
  }
  let ans = 0;
  for(let j = 1; j < nums.length; j++) {
    for(let i = 0; i < j; i++) {
      let commonDifference = nums[j] - nums[i];
      if ((commonDifference > (Math.pow(2, 31) - 1)) || commonDifference < (-Math.pow(2, 31))) {
        continue;
      }
      let apsEndingAtI = dp[i].get(commonDifference) || 0
      let apsEndingAtJ = dp[j].get(commonDifference) || 0
      
      dp[j].set(commonDifference, (apsEndingAtI + apsEndingAtJ + 1));
      ans += apsEndingAtI;
    }
  }
  return ans;
};

Approach) Two Pointer

Two-pointer approach to finding subsequences and store the number of occurrences in map

var numberOfArithmeticSlices = function(nums) {
    let cache = new Map();
    let result = 0;
    for(let i=0;i<nums.length;i++){
        cache[i] = new Map();
        for(let j=0;j<i;j++){
            let diff = nums[i]-nums[j];
            let iCache = cache[i].get(diff) || 0;
            let jCache = cache[j].get(diff) || 0;
            result+=jCache;
            cache[i].set(diff,iCache + jCache+1);
        }
    }
    return result;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 446. Arithmetic Slices II - Subsequence

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!