413. Arithmetic Slices
Model: qwen3.5:9b
Topics: Math,Dynamic Programming
FAANG asked: 1
Acceptance rate: 60.0%
Problem Breakdown
We need to count the number of contiguous subarrays within nums that form an arithmetic sequence. An arithmetic sequence requires at least three elements and a constant difference between adjacent pairs.
Inputs: A list of integers nums.
Outputs: The total integer count of valid arithmetic slices found in the array.
Constraints & Edge Cases to Consider:
- Length < 3: If the input has fewer than 3 elements, no slice can exist (return 0).
- Negative Numbers/Differences: Arithmetic sequences can have negative differences or zero difference (e.g.,
[7,7,7]). The logic must handlediff == 0correctly. - Overflow: Python handles large integers automatically, so standard integer overflow isn’t a concern here given the constraints ().
Intuition
A brute-force approach would iterate through every possible subarray (start and end indices) and check if it’s arithmetic. This results in or at best time complexity, which is inefficient for N=5000.
The key insight here relies on Dynamic Programming logic without necessarily needing a full DP table. Notice that an arithmetic slice ending at index i can only be formed if the difference between nums[i] - nums[i-1] matches the previous difference (nums[i-1] - nums[i-2]).
If this condition holds, we are extending existing valid sequences. Specifically:
- If a sequence of length (elements) ending at index is arithmetic, adding one more element that maintains the same difference creates exactly new slices ending at .
- Essentially, if we have found
xvalid arithmetic subarrays ending at positioni-1, and the current step continues the pattern, then there are nowx+1valid subarrays ending ati. If the pattern breaks (difference changes), any sequence of length cannot continue, so our running counter resets to 0.
Approach
We will iterate through the array starting from index 2 (since we need a minimum of 3 elements). We maintain two variables:
total_slices: Accumulates the final answer.current_run: Tracks how many arithmetic slices end at the current position.
For each element, calculate the difference between it and its predecessor (diff). Compare this to the previous difference stored in a variable (let’s call it prev_diff or just check against the last valid step).
- If
nums[i] - nums[i-1] == prev_diff: Incrementcurrent_run. Addcurrent_runtototal_slices. - Else: Reset
current_runto 0.
We need a way to track if we are currently in an arithmetic run, so I’ll initialize the loop logic carefully or handle index 2 separately. A cleaner implementation initializes prev_diff inside the loop or handles indices and . Given Python’s flexibility, iterating from index 2 is straightforward provided we track differences correctly.
Complexity Analysis
- Time: - We traverse the array exactly once with a single pass.
- Space: - We only use two integer variables (
total_slices,current_run) regardless of input size (excluding recursion stack or DP table).
Solution
def numberOfArithmeticSlices(nums):
# If fewer than 3 elements, no arithmetic slice is possible.
if len(nums) < 3:
return 0
total_slices = 0
current_run = 0
# We need at least indices i-2 and i to calculate a difference sequence.
# Start loop from index 2 (the third element).
for i in range(2, len(nums)):
diff_curr = nums[i] - nums[i-1]
if diff_curr == (nums[i-1] - nums[i-2]):
current_run += 1
total_slices += current_run
else:
# Pattern broken; reset the running counter for this position.
current_run = 0
return total_slices
Edge Cases Handled
- Length < 3: The initial check
if len(nums) < 3returns 0 immediately, preventing index errors or incorrect counts on small arrays like[1]. - Constant Sequence (e.g.,
[7,7,7]): Difference is always 0. Logic holds because , incrementing the run correctly to count all sub-slices of identical elements. - Negative Differences: Subtraction handles negative numbers naturally in Python; e.g.,
[-1,-3,-5]yields diff-2, which matches consistently across steps.