Arithmetic Slices - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given an integer array and need to count how many contiguous subarrays form an arithmetic sequence. A subarray is considered an arithmetic slice if it has at least three elements and the difference between consecutive elements is constant.
Approach 1: Iterative Check with Sliding Window (O(n) time, O(1) space)
Scan the array while tracking the difference between adjacent elements. When nums[i] - nums[i-1] equals nums[i-1] - nums[i-2], the current element extends an existing arithmetic slice. Every extension adds new valid subarrays ending at index i. Maintain a running counter of how many slices end at the current position and accumulate it into the total answer. If the difference changes, reset the counter because the arithmetic pattern breaks. This works well because every arithmetic subarray is determined by a continuous run of equal differences. Time complexity is O(n) since you iterate once through the array, and space complexity is O(1). This technique closely resembles a sliding window pattern applied to an array.
Approach 2: Dynamic Programming (O(n) time, O(n) space)
Define dp[i] as the number of arithmetic slices ending at index i. If the difference between nums[i] and nums[i-1] matches the difference between nums[i-1] and nums[i-2], then any arithmetic slice ending at i-1 can extend to i. That gives the recurrence dp[i] = dp[i-1] + 1. Otherwise, set dp[i] = 0 because the sequence breaks. Sum all values in the dp array to get the total number of slices. This formulation makes the recurrence explicit and is a common pattern in dynamic programming problems where substructures build on previous states. Time complexity remains O(n), but space complexity is O(n) due to the DP array.
Recommended for interviews: Interviewers usually expect the linear scan solution with a running count. It demonstrates that you recognize how arithmetic runs extend and how many new slices each extension contributes. Implementing the DP formulation first is acceptable during interviews because it clearly expresses the recurrence, then optimizing it to constant space shows strong problem-solving ability.
Approach 1: Dynamic Programming Approach
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.
This Python solution iterates through the array starting from the third element. It uses a variable dp to keep track of the number of subarrays ending at the current index that are arithmetic. If the difference between the current element and the previous element is the same as the previous difference, dp is incremented. Otherwise, it is reset to zero. The result is accumulated in total_slices.
Code
Python
Java
C++
C#
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using only constant space.
Approach 2: Iterative Check with Sliding Window
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.
This solution calculates the difference between every two consecutive elements d and checks if the subsequent elements maintain this difference. If they do, it increments the count of arithmetic subarrays. It stops the inner loop early if the difference condition breaks, optimizing from the naive complete enumeration.
Code
Python
Java
C++
C#
JavaScript
Complexity
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.
Approach 3: Iteration and Counting
We use d to represent the current difference between two adjacent elements, and cnt to represent the length of the current arithmetic sequence. Initially, d = 3000, cnt = 2.
We iterate through the array nums. For two adjacent elements a and b, if b - a = d, it means that the current element b also belongs to the current arithmetic sequence, and we increment cnt by 1. Otherwise, it means that the current element b does not belong to the current arithmetic sequence, and we update d = b - a, and cnt = 2. If cnt \ge 3, it means that the length of the current arithmetic sequence is at least 3, and the number of arithmetic sequences is cnt - 2, which we add to the answer.
After the iteration, we can get the answer.
In the code implementation, we can also initialize cnt to 0, and when resetting cnt, we directly set cnt to 0. When adding to the answer, we directly add cnt.
The time complexity is O(n), and the space complexity is O(1). Where n is the length of the array nums.
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the array. |
| Iterative Check with Sliding Window | Time Complexity: O(n^2) in the worst case, because we loop through pairs of start and end indices with an early exit. |
| Iteration and Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Check with Sliding Window | O(n) | O(1) | Best general solution. Efficient single pass and minimal memory. |
| Dynamic Programming | O(n) | O(n) | Useful when explaining recurrence or learning DP state transitions. |
Video Solution
Arithmetic Slices • Pepcoding • 19,234 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Arithmetic Slices easy or hard?
Arithmetic Slices Python/Java solution
How to solve Arithmetic Slices in O(n)?
What is the best approach for Arithmetic Slices?
Is Arithmetic Slices asked at Google/Amazon/Meta?
What data structure is used in Arithmetic Slices?
What is the time complexity of Arithmetic Slices?
Ready to solve this problem?
Practice Arithmetic Slices with our built-in code editor and test cases.
Practice on FleetCode