Arithmetic Slices — Solution in Python, Java & C++
Arithmetic Slices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Arithmetic Slices is a medium coding problem on arrays and dynamic programming, asked in Amazon, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An integer array is arithmetic if it has at least three elements and the difference between consecutive elements is constant.
Given an integer array nums, return the number of arithmetic subarrays (contiguous slices).
Example 1
Input: nums = [1,2,3,4]
Output: 3
Explanation: The slices are [1,2,3], [2,3,4] and [1,2,3,4].
Example 2
Input: nums = [1]
Output: 0
Example 3
Input: nums = [1,3,5,7,9]
Output: 6
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000
Hints for Arithmetic Slices
Hint 1
Let
curbe the number of arithmetic slices ending at the current index.Hint 2
If the current difference matches the previous one,
curgrows by one; otherwise it resets to zero.Hint 3
The answer is the running sum of
cur— each step adds the slices that end right there.
How to solve Arithmetic Slices
Let cur be the number of arithmetic slices ending at the current index; it grows by one while the difference matches and resets otherwise. Sum cur over the array.
Approach
- For
ifrom 2: ifnums[i] - nums[i-1] == nums[i-1] - nums[i-2],cur += 1andtotal += cur; elsecur = 0. - Return
total.
Why it works
If the arithmetic run ending at i has length L ≥ 3, exactly L - 2 slices end at i, which is what cur counts after each extension.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Slices of length 2 do not count.
Reference solution
Python
def numberOfArithmeticSlices(nums) -> int:
total = cur = 0
for i in range(2, len(nums)):
if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
cur += 1
total += cur
else:
cur = 0
return totalJava
public static int numberOfArithmeticSlices(int[] nums) {
int total = 0, cur = 0;
for (int i = 2; i < nums.length; i++) {
if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
cur++;
total += cur;
} else {
cur = 0;
}
}
return total;
}C++
int numberOfArithmeticSlices(vector<int>& nums) {
int total = 0, cur = 0;
for (int i = 2; i < (int) nums.size(); i++) {
if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
cur++;
total += cur;
} else {
cur = 0;
}
}
return total;
}JavaScript
var numberOfArithmeticSlices = function(nums) {
let total = 0, cur = 0;
for (let i = 2; i < nums.length; i++) {
if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
cur++;
total += cur;
} else {
cur = 0;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming