446. Arithmetic Slices II – Subsequence LeetCode Solution

In this guide, you will get 446. Arithmetic Slices II – Subsequence LeetCode Solution with the best time and space complexity. The solution to Arithmetic Slices II – Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Arithmetic Slices II – Subsequence solution in C++
Arithmetic Slices II – Subsequence solution in Java
Arithmetic Slices II – Subsequence solution in Python
Additional Resources

446. Arithmetic Slices II - Subsequence LeetCode Solution image

Problem Statement of Arithmetic Slices II – Subsequence

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

446. Arithmetic Slices II – Subsequence LeetCode Solution in C++

class Solution {
 public:
  int numberOfArithmeticSlices(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    // dp[i][j] := the number of subsequences end in nums[j] nums[i]
    vector<vector<int>> dp(n, vector<int>(n));
    unordered_map<long, vector<int>> numToIndices;

    for (int i = 0; i < n; ++i)
      numToIndices[nums[i]].push_back(i);

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        const long target = nums[j] * 2L - nums[i];
        if (const auto it = numToIndices.find(target);
            it != numToIndices.cend())
          for (const int k : it->second)
            if (k < j)
              dp[i][j] += (dp[j][k] + 1);
        ans += dp[i][j];
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

446. Arithmetic Slices II – Subsequence LeetCode Solution in Java

class Solution {
  public int numberOfArithmeticSlices(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    // dp[i][j] := the number of subsequences end in nums[j] nums[i]
    int[][] dp = new int[n][n];
    Map<Long, List<Integer>> numToIndices = new HashMap<>();

    for (int i = 0; i < n; ++i) {
      numToIndices.putIfAbsent((long) nums[i], new ArrayList<>());
      numToIndices.get((long) nums[i]).add(i);
    }

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        final long target = nums[j] * 2L - nums[i];
        if (numToIndices.containsKey(target))
          for (final int k : numToIndices.get(target))
            if (k < j)
              dp[i][j] += (dp[j][k] + 1);
        ans += dp[i][j];
      }

    return ans;
  }
}
// code provided by PROGIEZ

446. Arithmetic Slices II – Subsequence LeetCode Solution in Python

class Solution:
  def numberOfArithmeticSlices(self, nums: list[int]) -> int:
    n = len(nums)
    ans = 0
    # dp[i][j] := the number of subsequences end in nums[j] nums[i]
    dp = [[0] * n for _ in range(n)]
    numToIndices = collections.defaultdict(list)

    for i, num in enumerate(nums):
      numToIndices[num].append(i)

    for i in range(n):
      for j in range(i):
        target = nums[j] * 2 - nums[i]
        if target in numToIndices:
          for k in numToIndices[target]:
            if k < j:
              dp[i][j] += dp[j][k] + 1
        ans += dp[i][j]

    return ans
 # code by PROGIEZ