Arithmetic Slices

MEDIUM

Description

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

Checkout 3 different approaches to solve Arithmetic Slices. Click on different approaches to view the approach and algorithm in detail.

Refined Brute Force

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.

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 count to 0.
Iterate with an outer loop from i = 0 to nums.length - 2. This i will be the starting index of our potential slices.
For each i, calculate the required common difference diff = nums[i + 1] - nums[i].
Start an inner loop with j from i + 2 to nums.length - 1.
In the inner loop, check if nums[j] - nums[j - 1] is equal to diff.
If they are equal, it means the subarray nums[i...j] is an arithmetic slice. So, we increment our count.
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.
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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the count and difference, not dependent on the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Arithmetic Slices. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Arithmetic Slices

Patterns:

Sliding WindowDynamic Programming

Data Structures:

Array

Companies:

Baidu |