algoadvance

Leetcode 413. Arithmetic Slices

Problem Statement

Given an integer array nums, return the number of arithmetic subarrays of nums.

An arithmetic array is any contiguous subarray of nums where the difference between the consecutive elements is the same.

Example:

Input: nums = [1, 2, 3, 4]
Output: 3
Explanation: We have three arithmetic slices in [1, 2, 3, 4]: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Clarifying Questions

  1. Q: What is the minimum constraint on the length of the input array? A: The input array nums will have at least 1 element.

  2. Q: Can the input array contain negative numbers and zero? A: Yes, the input array can contain any integers, including negative numbers and zero.

  3. Q: What is the maximum length of the array? A: Typically, for LeetCode problems, the array length might go up to 10,000 or more, but we’ll write a general solution that should work within these common constraints.

Strategy

We can solve this problem using a dynamic programming approach. Here is a step-by-step plan:

  1. Initialize a counter to keep track of the total arithmetic slices.
  2. Traverse the array while checking for arithmetic slices:
    • For each possible slice, calculate the difference between consecutive elements.
    • If the difference remains constant for at least 3 elements (i.e., the minimum number needed for an arithmetic slice), it’s a valid slice.
  3. Track the number of valid slices that end at each position using a variable.
  4. Sum up all valid slices found during the traversal.

Code

Here’s a C++ function to solve the problem:

#include <vector>
using namespace std;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        
        if (n < 3) return 0;  // An arithmetic slice must have at least 3 elements
        
        int totalSlices = 0;
        int currentSlices = 0;

        for (int i = 2; i < n; ++i) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                ++currentSlices;
                totalSlices += currentSlices;
            } else {
                currentSlices = 0;
            }
        }

        return totalSlices;
    }
};

Time Complexity

This approach efficiently counts all arithmetic slices in a single pass through the array, leveraging the property of continuous arithmetic sequences.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI