Arithmetic Slices

medium array dp

Problem

Count the number of contiguous subarrays of length ≥ 3 whose consecutive differences are all equal (arithmetic progressions).

Inputnums = [1, 2, 3, 4]

Output3

Slices: [1,2,3], [2,3,4], [1,2,3,4].

nums (comma-separated)

def number_of_arithmetic_slices(nums):
    total, run = 0, 0
    for i in range(2, len(nums)):
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
            run += 1
            total += run
        else:
            run = 0
    return total

function numberOfArithmeticSlices(nums) {
  let total = 0, run = 0;
  for (let i = 2; i < nums.length; i++) {
    if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
      run++;
      total += run;
    } else {
      run = 0;
    }
  }
  return total;
}

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

int numberOfArithmeticSlices(vector<int>& nums) {
    int total = 0, run = 0;
    for (int i = 2; i < (int)nums.size(); i++) {
        if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
            run++;
            total += run;
        } else run = 0;
    }
    return total;
}

Explanation

We count contiguous subarrays of length ≥ 3 whose neighboring differences are all equal. Instead of checking every subarray, we walk once and track how long the current arithmetic run is.

At each position i we ask: does nums[i] continue the same difference as before, i.e. nums[i] - nums[i-1] == nums[i-1] - nums[i-2]? If yes, the run grows.

The neat counting fact: whenever a run extends by one element, the number of new valid slices ending right here equals the current run length run. So we do run += 1 and total += run.

If the difference breaks, the run resets to 0 and we start fresh from the next triple.

Example: nums = [1,2,3,4]. At index 2 the difference holds, run = 1, total = 1 (slice [1,2,3]). At index 3 it still holds, run = 2, total = 3 (adding [2,3,4] and [1,2,3,4]) → answer 3.

Time: O(n) Space: O(1)