Solution Explanation: 413. Arithmetic Slices

This problem asks to find the number of arithmetic subarrays within a given integer array. An arithmetic subarray is defined as a contiguous subsequence containing at least three elements where the difference between consecutive elements is constant.

Approach: Iteration and Counting

The most efficient approach is a single-pass iterative solution that keeps track of the current arithmetic sequence's length. We don't need to explicitly enumerate all subarrays; instead, we incrementally count arithmetic slices as we traverse the array.

Algorithm:

1. Initialization:

   • ans: Stores the total count of arithmetic slices (initialized to 0).
   • cnt: Keeps track of the length of the current arithmetic sequence (initialized to 0). Some implementations initialize to 2.
   • d: Stores the common difference between consecutive elements in the current arithmetic sequence (initialized to a value unlikely to be a real difference, like 3000).

2. Iteration:

   • Iterate through the nums array using a sliding window of size 2 (comparing adjacent elements).
   • Check for Arithmetic Progression: For each pair of adjacent elements (a, b):
     • If b - a == d, it means the current element extends the existing arithmetic sequence. Increment cnt.
     • Otherwise, it signifies the end of the current arithmetic sequence. Update d to the new difference (b - a) and reset cnt to 0 or 1 (depending on implementation).
   • Update ans: If cnt is greater than or equal to 2 (meaning we have at least an arithmetic slice), add cnt (or cnt - 2 depending on initialization of cnt) to ans.

3. Return ans: The final value of ans represents the total number of arithmetic slices.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array only once.

Space Complexity: O(1). We use only a few constant extra variables.

Code Implementations

The following code snippets demonstrate the solution in various programming languages:

Python3

from itertools import pairwise
 
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        ans = cnt = 0
        d = 3000  # Initialize to an unlikely difference
        for a, b in pairwise(nums):
            if b - a == d:
                cnt += 1
            else:
                d = b - a
                cnt = 0 # Reset for a new sequence
            ans += cnt # Add the number of slices found so far in this sequence
        return ans
 

Java

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int ans = 0, cnt = 0;
        int d = 3000; // Initialize to an unlikely difference
        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; // Reset for a new sequence
            }
            ans += cnt; // Add the number of slices found so far in this sequence
        }
        return ans;
    }
}

C++

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int ans = 0, cnt = 0;
        int d = 3000; // Initialize to an unlikely difference
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i + 1] - nums[i] == d) {
                ++cnt;
            } else {
                d = nums[i + 1] - nums[i];
                cnt = 0; // Reset for a new sequence
            }
            ans += cnt; // Add the number of slices found so far in this sequence
        }
        return ans;
    }
};

(Go, TypeScript, and other languages would follow a similar structure.)

The code in all languages implements the same core algorithm. The differences are mainly in syntax and standard library functions used (like pairwise in Python). The key idea remains consistent: iterating through the array, efficiently counting arithmetic slices without redundant subarray checks.