Arithmetic Slices
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through all possible starting elements of an arithmetic subarray. For each starting element, it extends the subarray to the right, one element at a time, and checks if the arithmetic property is maintained. If it is, a valid arithmetic slice has been found, and the count is incremented.
Algorithm
- Initialize a counter
countto 0. - Iterate with an outer loop for
ifrom0tonums.length - 3. - For each
i, calculate the common differencediff = nums[i + 1] - nums[i]. - Start an inner loop with
jfromi + 2tonums.length - 1. - If
nums[j] - nums[j - 1] == diff, it means the subarraynums[i...j]is an arithmetic slice, so incrementcount. - If the differences are not equal, any longer subarray starting at
icannot be arithmetic, so break the inner loop. - After the loops complete, return
count.
Walkthrough
We can fix the starting index i of a potential arithmetic subarray and then iterate through the subsequent elements to find all valid arithmetic subarrays that begin at i.
The algorithm works as follows:
- Initialize a counter
countto 0. - Iterate with an outer loop from
i = 0tonums.length - 2. Thisiwill be the starting index of our potential slices. - For each
i, calculate the required common differencediff = nums[i + 1] - nums[i]. - Start an inner loop with
jfromi + 2tonums.length - 1. - In the inner loop, check if
nums[j] - nums[j - 1]is equal todiff. - If they are equal, it means the subarray
nums[i...j]is an arithmetic slice. So, we increment ourcount. - If they are not equal, it means any longer subarray starting at
icannot be arithmetic. We can break the inner loop and move to the next starting indexi. - After all loops complete,
countwill hold the total number of arithmetic subarrays.
class Solution { public int numberOfArithmeticSlices(int[] nums) { if (nums.length < 3) { return 0; } int count = 0; for (int i = 0; i < nums.length - 2; i++) { int diff = nums[i + 1] - nums[i]; for (int j = i + 2; j < nums.length; j++) { if (nums[j] - nums[j - 1] == diff) { count++; } else { break; } } } return count; }}Complexity
Time
O(n^2), where n is the length of the input array. The two nested loops give a quadratic time complexity in the worst case.
Space
O(1), as we only use a few variables to store the count and difference, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Improves upon the naive O(n^3) brute-force approach.
Uses constant extra space.
Cons
Inefficient for large inputs due to the quadratic time complexity.
Performs many redundant checks. For example, when checking
[1,2,3,4], the check for[2,3,4]being arithmetic is repeated.
Solutions
Solution
class Solution {public int numberOfArithmeticSlices(int[] nums) { int ans = 0, cnt = 0; int d = 3000; for (int i = 0; i < nums.length - 1; ++i) { if (nums[i + 1] - nums[i] == d) { ++cnt; } else { d = nums[i + 1] - nums[i]; cnt = 0; } ans += cnt; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.