We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Arithmetic Triplets

Number: 2442

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a strictly increasing integer array named nums and a positive integer diff, count the number of unique arithmetic triplets (i, j, k) such that i < j < k, nums[j] - nums[i] equals diff, and nums[k] - nums[j] equals diff.

Key Insights

  • The array is strictly increasing which means no duplicates exist.
  • For any number, we can quickly determine if a valid arithmetic triplet exists by checking if number+diff and number+2*diff are present.
  • Using a hash set allows constant time look-up for the needed elements.
  • Alternatively, two pointers could be utilized, but the set approach simplifies the arithmetic progression check.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array, as each element is checked and set look-up is O(1). Space Complexity: O(n) for storing the numbers in a hash set.

Solution

We iterate through each number in the array and use a hash set to check if both number + diff and number + 2 * diff exist. If they do, the triplet is counted. This approach leverages constant-time look-ups provided by the hash set, ensuring an efficient and clear solution.

Code Solutions

# Function to count number of arithmetic triplets
def arithmeticTriplets(nums, diff):
    # Create a set of nums for O(1) look-up
    nums_set = set(nums)
    count = 0  # Initialize counter for arithmetic triplets
    
    # Iterate over each number in the array
    for num in nums:
        # Check if the successive elements in the progression exist
        if (num + diff in nums_set) and (num + 2 * diff in nums_set):
            count += 1   # Increment count if valid triplet is found
    
    return count

# Example usage:
print(arithmeticTriplets([0,1,4,6,7,10], 3))  # Expected Output: 2
← Back to All Questions