Scale Engineer

Arithmetic Slices

Med
#0400Time: 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.1 company
Patterns
Sliding WindowDynamic Programming
Data structures
Array
Companies
Baidu

Prompt

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 count to 0.
  • Iterate with an outer loop for i from 0 to nums.length - 3.
  • For each i, calculate the common difference diff = nums[i + 1] - nums[i].
  • Start an inner loop with j from i + 2 to nums.length - 1.
  • If nums[j] - nums[j - 1] == diff, it means the subarray nums[i...j] is an arithmetic slice, so increment count.
  • If the differences are not equal, any longer subarray starting at i cannot 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:

  1. Initialize a counter count to 0.
  2. Iterate with an outer loop from i = 0 to nums.length - 2. This i will be the starting index of our potential slices.
  3. For each i, calculate the required common difference diff = nums[i + 1] - nums[i].
  4. Start an inner loop with j from i + 2 to nums.length - 1.
  5. In the inner loop, check if nums[j] - nums[j - 1] is equal to diff.
  6. If they are equal, it means the subarray nums[i...j] is an arithmetic slice. So, we increment our count.
  7. If they are not equal, it means any longer subarray starting at i cannot be arithmetic. We can break the inner loop and move to the next starting index i.
  8. After all loops complete, count will 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

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.

← Previous

Previous problem

Next →

Next problem