In this guide, you will get 413. Arithmetic Slices LeetCode Solution with the best time and space complexity. The solution to Arithmetic Slices 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.
An integer array 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.
Given an integer array nums, return the number of arithmetic subarrays of nums.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.
Example 2:
Input: nums = [1]
Output: 0
Constraints:
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
413. Arithmetic Slices LeetCode Solution in C++
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
const int n = nums.size();
if (n < 3)
return 0;
vector<int> dp(
n); // dp[i] := the number of arithmetic slices ending in index i
for (int i = 2; i < nums.size(); ++i)
if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
dp[i] = dp[i - 1] + 1;
return accumulate(dp.begin(), dp.end(), 0);
}
}; /* code provided by PROGIEZ */
413. Arithmetic Slices LeetCode Solution in Java
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
final int n = nums.length;
if (n < 3)
return 0;
int[] dp = new int[n]; // dp[i] := the number of arithmetic slices ends in nums[i]
for (int i = 2; i < n; ++i)
if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
dp[i] += dp[i - 1] + 1;
return Arrays.stream(dp).sum();
}
} // code provided by PROGIEZ
413. Arithmetic Slices LeetCode Solution in Python
class Solution:
def numberOfArithmeticSlices(self, nums: list[int]) -> int:
n = len(nums)
if n < 3:
return 0
dp = [0] * n # dp[i] := the number of arithmetic slices ending in index i
for i in range(2, len(nums)):
if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
dp[i] = dp[i - 1] + 1
return sum(dp) # code by PROGIEZ
