algoadvance

Leetcode 413. Arithmetic Slices

Problem Statement

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.

Example

Clarifying Questions

  1. What is the range of values for the elements in nums?
    • The elements in nums are integers. The exact range is not specified, but this algorithm should handle typical integer ranges.
  2. What is the length range of the input array nums?
    • The array length should be at least 1 and up to a large number typical of problem constraints, possibly around 10,000.

Strategy

  1. Understand that an arithmetic subarray has a constant difference d between consecutive elements.
  2. Iterate through the array while keeping track of the current length of the arithmetic subarray:
    • Maintain a count of consecutive elements that form an arithmetic sequence.
    • Use two pointers or a sliding window to identify subarrays with common differences.
  3. For each valid arithmetic subarray found, count the possible arithmetic subarrays it can contribute, extending them as you go.

Code

public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;  // There need to be at least three to form an arithmetic subarray

        int totalCount = 0;
        int currentCount = 0;

        // Loop through the array while comparing differences
        for (int i = 2; i < n; i++) {
            // Check if the current element, along with the previous two, form an arithmetic sequence
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                currentCount += 1;
                totalCount += currentCount;  // Accumulate the arithmetic subarrays ending at `i`
            } else {
                currentCount = 0;  // Reset the current arithmetic subarray count
            }
        }

        return totalCount;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums1 = {1, 2, 3, 4};  // Expected output: 3
        System.out.println(sol.numberOfArithmeticSlices(nums1));

        int[] nums2 = {1, 3, 5, 7, 9};  // Expected output: 6
        System.out.println(sol.numberOfArithmeticSlices(nums2));
    }
}

Time Complexity

This solution efficiently finds all possible arithmetic subarrays by keeping track of the ongoing sequences and counting them as we go.

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