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.
[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] <= 1000The key idea in Arithmetic Slices is to identify contiguous subarrays where the difference between consecutive elements remains constant. An arithmetic slice must have a length of at least three. Instead of checking every possible subarray, which would be inefficient, we can observe that if three consecutive numbers maintain the same difference, the slice can extend further as long as the pattern continues.
A common strategy uses dynamic programming or a lightweight sliding window idea. As you iterate through the array, compare differences like nums[i] - nums[i-1] and nums[i-1] - nums[i-2]. If they match, the current element extends previously found arithmetic slices. You keep track of how many valid slices end at the current index and accumulate the result.
This incremental counting avoids recomputation and allows the problem to be solved efficiently in linear time with minimal extra memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (incremental counting) | O(n) | O(1) |
| Sliding Window / Difference Tracking | O(n) | O(1) |
Pepcoding
The idea is to use dynamic programming to count the number of arithmetic subarrays ending at each position in the array. By traversing from the start to the end of the array, we can keep track of how many arithmetic subarrays end at each index by considering the difference of current and previous elements.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using only constant space.
1#include <vector>
2using namespace std;
3class Solution {
4public:
5 int numberOfArithmeticSlices(vector<int>& nums) {
6 int n = nums.size();
7 if (n < 3) return 0;
8 int dp = 0, totalSlices = 0;
9 for (int i = 2; i < n; ++i) {
10 if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
11 dp += 1;
12 totalSlices += dp;
13 } else {
14 dp = 0;
15 }
16 }
17 return totalSlices;
18 }
19};
20This C++ solution mimics the dynamic programming approach. It initializes a zero counter dp and updates it by iterating through the array, adding to totalSlices whenever consecutive differences match as required.
This approach uses a double loop to consider all subarrays of length greater than or equal to 3. A sliding window technique checks each possible subarray in fewer operations. This approach is less optimal in terms of time complexity compared to dynamic programming, but it provides a clear and direct method to check subarrays.
Time Complexity: O(n^2) in the worst case, because we loop through pairs of start and end indices with an early exit.
Space Complexity: O(1), using constant extra space.
1functionWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of Arithmetic Slices or similar pattern-based array problems appear in technical interviews at top companies. Interviewers use it to test pattern recognition, dynamic programming intuition, and efficient iteration through arrays.
The optimal approach scans the array once and tracks whether the difference between consecutive elements remains constant. Using a dynamic programming idea, you count how many arithmetic slices end at each index and accumulate the total. This reduces the complexity to O(n) time with O(1) space.
Dynamic programming is used because the number of arithmetic slices ending at the current index depends on the count from the previous index. If the difference pattern continues, previous results can be extended instead of recalculating from scratch.
No complex data structure is required. The problem mainly relies on array traversal and tracking differences between adjacent elements, often using a few variables to maintain counts of valid slices.
This JavaScript implementation follows a nested loop strategy to assess and count every possible arithmetic subarray. It exits the inner loop early upon detecting a break in arithmetic continuity.