Number of Arithmetic Triplets

Difficulty: Easy | Acceptance: 85.50% | Paid: No Topics: Array, Hash Table, Two Pointers, Enumeration

You are given a 0-indexed, strictly increasing integer array nums and a positive integer diff.

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

i < j < k, nums[j] - nums[i] == diff, and nums[k] - nums[j] == diff. Return the number of unique arithmetic triplets.

• Examples
• Constraints
• Brute Force Enumeration
• Hash Set Lookup
• Two Pointers
• Binary Search

Examples

Example 1:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.

Example 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation:
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.

Constraints

3 <= nums.length <= 200
0 <= nums[i] <= 200
1 <= diff <= 50
nums is strictly increasing.

Brute Force Enumeration

Intuition Since the constraints are small (nums.length <= 200), we can simply check every possible combination of three indices (i, j, k) to see if they satisfy the arithmetic conditions.

Steps

• Initialize a counter to 0.
• Use three nested loops to iterate through all possible triplets (i, j, k) such that i < j < k.
• For each triplet, check if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff.
• If the condition is met, increment the counter.
• Return the counter.

class Solution:
    def arithmeticTriplets(self, nums: list[int], diff: int) -> int:
        n = len(nums)
        count = 0
        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:
                        count += 1
        return count

Complexity

• Time: O(n³) — We iterate through three nested loops.
• Space: O(1) — We only use a few variables for counting.
• Notes: Simple to implement but inefficient for large arrays.

Hash Set Lookup

Intuition We can optimize the lookup process by storing all numbers in a hash set. For any number num in the array, if num - diff and num + diff both exist in the set, then num is the middle element of a valid arithmetic triplet.

Steps

• Create a hash set containing all elements from nums.
• Initialize a counter to 0.
• Iterate through each number num in nums.
• Check if num - diff is in the set AND num + diff is in the set.
• If both exist, increment the counter.
• Return the counter.

class Solution:
    def arithmeticTriplets(self, nums: list[int], diff: int) -> int:
        num_set = set(nums)
        count = 0
        for num in nums:
            if (num - diff) in num_set and (num + diff) in num_set:
                count += 1
        return count

Complexity

• Time: O(n) — Iterating through the array and set lookups take O(1) on average.
• Space: O(n) — We store all elements in a hash set.
• Notes: Very efficient time complexity, but trades off space for time.

Two Pointers

Intuition Since the array is strictly increasing, we can use two pointers to find the required elements for each middle element nums[j]. We can move pointers i and k to find values that match the difference diff.

Steps

• Initialize count to 0.
• Iterate through the array with index j acting as the middle element.
• Initialize pointer i to 0 and k to nums.length - 1.
• While i < j and nums[j] - nums[i] > diff, increment i.
• While k > j and nums[k] - nums[j] > diff, decrement k.
• Check if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff. If so, increment count.
• Return count.

class Solution:
    def arithmeticTriplets(self, nums: list[int], diff: int) -> int:
        n = len(nums)
        count = 0
        for j in range(n):
            i = 0
            while i < j and nums[j] - nums[i] > diff:
                i += 1
            k = n - 1
            while k > j and nums[k] - nums[j] > diff:
                k -= 1
            if i < j and k > j and nums[j] - nums[i] == diff and nums[k] - nums[j] == diff:
                count += 1
        return count

Complexity

• Time: O(n²) — In the worst case, pointers traverse the array for each j.
• Space: O(1) — No extra space used.
• Notes: Efficient space usage, though slightly slower than the hash set approach.

Binary Search

Intuition Since the array is sorted, for each middle element nums[j], we can use binary search to check if nums[j] - diff exists in the left subarray and nums[j] + diff exists in the right subarray.

Steps

• Initialize count to 0.
• Iterate through the array with index j.
• Perform a binary search for nums[j] - diff in the range [0, j).
• Perform a binary search for nums[j] + diff in the range (j, n).
• If both elements are found, increment count.
• Return count.

import bisect

class Solution:
    def arithmeticTriplets(self, nums: list[int], diff: int) -> int:
        n = len(nums)
        count = 0
        for j in range(n):
            left = nums[j] - diff
            right = nums[j] + diff
            
            i = bisect.bisect_left(nums, left, 0, j)
            k = bisect.bisect_left(nums, right, j + 1, n)
            
            if i < j and nums[i] == left and k < n and nums[k] == right:
                count += 1
        return count

Complexity

• Time: O(n log n) — Binary search takes O(log n) and we perform it n times.
• Space: O(1) — No extra space used.
• Notes: Good balance of time and space, leveraging the sorted property of the array.