Code Implementation

class Solution:
    def numberOfArithmeticSlices(self, nums):
        n = len(nums)
        if n < 3:
            return 0
        count = 0
        curr = 0
        for i in range(2, n):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                curr += 1
                count += curr
            else:
                curr = 0
        return count
      

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        int count = 0, curr = 0;
        for (int i = 2; i < n; ++i) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                curr += 1;
                count += curr;
            } else {
                curr = 0;
            }
        }
        return count;
    }
};
      

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;
        int count = 0, curr = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                curr++;
                count += curr;
            } else {
                curr = 0;
            }
        }
        return count;
    }
}
      

var numberOfArithmeticSlices = function(nums) {
    let n = nums.length;
    if (n < 3) return 0;
    let count = 0, curr = 0;
    for (let i = 2; i < n; i++) {
        if (nums[i] - nums[i-1] === nums[i-1] - nums[i-2]) {
            curr++;
            count += curr;
        } else {
            curr = 0;
        }
    }
    return count;
};
      

Problem Description

Given an array of integers nums, your task is to return the number of arithmetic slices in nums.
An arithmetic slice is a subarray with at least three elements where the difference between any two consecutive elements is the same. In other words, for any subarray nums[i], nums[i+1], ..., nums[j] (where j - i + 1 >= 3), the difference nums[k+1] - nums[k] must be constant for all valid k.

• You must count only contiguous subarrays (slices).
• Each element of nums can be used in multiple slices, but each slice is counted only once.
• The input array nums can contain positive, negative, or zero values.

Thought Process

To solve this problem, we first need to understand what constitutes an arithmetic slice. The key observation is that any subarray of length 3 or more, where the difference between consecutive elements is constant, is a valid slice.
A brute-force approach would be to check every possible subarray of length at least 3, and for each, verify if it is arithmetic. However, this approach is inefficient for large arrays.
Instead, we look for patterns: if three consecutive elements form an arithmetic sequence, so do the last three of any longer sequence with the same difference. This means we can build upon previously found arithmetic slices, counting how many new ones are formed as we extend the sequence.
This leads to an optimized approach where, as we scan through the array, we keep track of how many arithmetic slices end at each position, and accumulate the total.

Solution Approach

• Step 1: Initialize two variables: count for the total number of arithmetic slices, and curr for the number of arithmetic slices ending at the current index.
• Step 2: Iterate from the third element (index 2) to the end of the array.
• Step 3: For each index i, check if nums[i] - nums[i-1] equals nums[i-1] - nums[i-2]. If true, it means the current three elements form an arithmetic sequence.
• Step 4: If the current three elements are arithmetic, increment curr (since any previous slice ending at i-1 can be extended by nums[i]), and add curr to count.
• Step 5: If the current three elements do not form an arithmetic sequence, reset curr to 0.
• Step 6: After the loop, count contains the total number of arithmetic slices.

This approach is efficient because it avoids redundant checks and leverages the structure of arithmetic sequences to build longer slices from shorter ones.

Example Walkthrough

Consider the input nums = [1, 2, 3, 4].
Let's trace the iterations:

• At i = 2: nums[2] - nums[1] = 1, nums[1] - nums[0] = 1 (equal, so arithmetic). curr = 1, count = 1 (slice: [1,2,3])
• At i = 3: nums[3] - nums[2] = 1, nums[2] - nums[1] = 1 (equal, so arithmetic). curr = 2, count = 3 (slices: [2,3,4] and [1,2,3,4])

The arithmetic slices are: [1,2,3], [2,3,4], and [1,2,3,4] (which contains both previous slices). Thus, the answer is 3.

Time and Space Complexity

• Brute-force approach: For each possible subarray of length at least 3, check if it is arithmetic. There are O(n^2) such subarrays, and checking each takes O(1) time (if we precompute differences), so overall time is O(n^2). Space is O(1).
• Optimized approach (used here): We scan the array once, doing constant work at each step. Thus, time complexity is O(n), and space complexity is O(1), since we use only a couple of variables.

Summary

The key insight is that arithmetic slices can be counted efficiently by building on previously found slices as we iterate through the array. By keeping track of how many slices end at each position and extending them when possible, we achieve a linear-time solution. This method is both elegant and practical, making it suitable for large input sizes.