Arithmetic Slices
Medium · Dynamic Programming · Array · Dynamic Programming · Sliding Window
Problem
An array is arithmetic if it has at least three elements and every pair of neighbors has the same difference. [1,3,5,7], [7,7,7] and [3,-1,-5] are arithmetic; [1,1,2] is not.
Given an integer array nums, return the number of contiguous subarrays of nums that are arithmetic.
Examples
Input: nums = [1,3,5,7,8] Output: 3
They are [1,3,5], [3,5,7] and [1,3,5,7]. Nothing that includes 8 works, because 7 → 8 steps by 1.
Input: nums = [1,2,4] Output: 0
The differences 1 and 2 do not match.
Input: nums = [5,5,5,5] Output: 3
Two slices of length 3 and one of length 4, all with difference 0.
Constraints
- 1 <= len(nums) <= 5000
- -1000 <= nums[i] <= 1000
Approaches
- Baseline: extend from every start — time O(n²), space O(1)
Follow-up
If the slices did not have to be contiguous (any subsequence of length 3 or more with equal steps), the count can be exponential and needs a map per index from difference to count: an O(n²) DP. The use cases keep contiguity and ask for the longest run, and for slices with one given difference.
Related problems
Start free on Cariara · Coding problems · System design studio
