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.
[1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.[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.
[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 - 1This approach uses dynamic programming and hashmaps to calculate arithmetic subsequences efficiently. For each index, we maintain a hashmap that tracks the count of different differences (arithmetic differences) and the number of subsequences that end with that difference at the given index. This allows us to build potential subsequences as we iterate over the array.
This C solution involves using a 2D array `dp` where `dp[i][d]` represents the number of arithmetic subsequences ending at index `i` with common difference `d`. We iterate through pairs `(i, j)` where `j < i` and calculate the difference `d`. For each pair, we update the `dp` array and accumulate the answer in `res` by adding the count of subsequences ending at `j` with difference `d`.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the length of the input array.
Space Complexity: O(n * m), where m is the number of possible differences (limited by the constraint of 31-bit integer).
This approach considers all possible subsequences (using combinations) and checks if each subsequence is arithmetic. Although not efficient, it can be used to demonstrate the logic on small arrays to understand the problem better.
This C program generates all combinations as potential subsequences and checks whether each subsequence is arithmetic by comparing adjacent differences. Due to its combinatorial nature, this approach is inefficient for large inputs but helps in understanding smaller cases.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`.
Space Complexity: O(n) given additional space for combinations.
| Approach | Complexity |
|---|---|
| Dynamic Programming with HashMap | Time Complexity: O(n^2), where n is the length of the input array. |
| Brute Force Approach (Inefficient for Larger Inputs) | Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`. |
Arithmetic Slices II - Leetcode 446 - Python • NeetCodeIO • 17,990 views views
Watch 9 more video solutions →Practice Arithmetic Slices II - Subsequence with our built-in code editor and test cases.
Practice on FleetCode