Watch 10 video solutions for Arithmetic Slices, a medium level problem involving Array, Dynamic Programming, Sliding Window. This walkthrough by Pepcoding has 18,296 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1000Problem 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 | 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. |