Arithmetic Slices
Medium · Sliding Window · Explanation and code example
Count Arithmetic Runs Ending at Each Index
How it works
An arithmetic slice ending at i extends an earlier slice when the last two differences match. In that case, the previous ending count gains one new length-three slice. Summing the ending counts counts every contiguous arithmetic slice once.
Steps
- Compare the two newest adjacent differences.
- Set dp[i] = dp[i - 1] + 1 when they match, otherwise zero.
- Sum all ending counts.
Complexity
- Time: O(n).
- Space: O(n) for the shown DP arrays.
Things to watch for
- Slices must be contiguous and contain at least three values.
- Equal values form arithmetic slices with difference zero.
- Reset the count when the difference changes.
Python code example
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)
C++ code example
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);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.