algoadvance

You are given a 0-indexed integer array nums and an integer diff.

A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:

• i < j < k
• nums[j] - nums[i] == diff
• nums[k] - nums[j] == diff

Return the number of unique arithmetic triplets.

Example 1:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation:
(0, 1, 2), [0, 1, 4] and (1, 2, 3), [1, 4, 7] are the arithmetic triplets.

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation:
(0, 2, 4), [4, 6, 8] and (1, 3, 5), [5, 7, 9] are the arithmetic triplets.

Clarifying Questions

1. Can the input array contain negative numbers?
2. What is the maximum size of the input array?
3. Do we need to account for performance beyond considering a method that’s within typical constraints for competitive programming?

Strategy

1. Iterate through the array with three nested loops to find all possible triplets.
2. Check the conditions for arithmetic triplets.
3. An optimized approach considers using hash sets for lookup to achieve better time complexity.

Code

Let’s start with the simplest brute-force approach:

def arithmeticTriplets(nums, diff):
    triplet_count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff:
                    triplet_count += 1
    return triplet_count

Optimized Approach

1. Use a hash set to store the numbers we’ve seen so far.
2. Iterate through the array, and for each number, check if the required previous numbers are in the set.
3. This approach is much more efficient.

def arithmeticTriplets(nums, diff):
    num_set = set(nums)
    triplet_count = 0

    for num in nums:
        if (num - diff in num_set) and (num - 2 * diff in num_set):
            triplet_count += 1

    return triplet_count

Time Complexity

• The brute-force approach has a time complexity of (O(n^3)), where (n) is the length of the array.
• The optimized approach has a time complexity of (O(n)), due to the linear scan and hash set operations, which are average (O(1)) for insert and check.

Thus, the optimized approach is preferable for larger input sizes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?