Number of Arithmetic Triplets

🏠 ⬅️ ➡️

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 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.

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.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
⚠️ Correct 
program main
    implicit none

    integer, parameter :: n = 6
    integer, parameter :: diff = 3
    integer, dimension(n) :: nums
    integer :: i, j, k
    integer :: count

    ! Examples from the problem statement
    nums = [0, 1, 4, 6, 7, 10]
    write (*, '(A, I0)') 'Example 1: ', solve(nums, diff)
    nums = [4, 5, 6, 7, 8, 9]
    write (*, '(A, I0)') 'Example 2: ', solve(nums, diff)

contains

    function solve(nums, diff) result(count)
        implicit none
        integer, intent(in) :: nums(:), diff
        integer :: count
        integer :: i, j, k

        count = 0
        do i = 1, size(nums) - 2
            do j = i + 1, size(nums) - 1
                do k = j + 1, size(nums)
                    if (nums(k) - nums(j) == diff .and. &
                        nums(j) - nums(i) == diff) then
                        count = count + 1
                    end if
                end do
            end do
        end do
    end function solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module arithmetic_triplets
    implicit none
    private
    public :: arithmetic_triplets
contains
    function arithmetic_triplets(nums, diff) result(count)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: diff
        integer :: count
        integer :: i, j, k

        count = 0
        do i = 1, size(nums) - 2
            do j = i + 1, size(nums) - 1
                do k = j + 1, size(nums)
                    if (nums(j) - nums(i) == diff .and. nums(k) - nums(j) == diff) then
                        count = count + 1
                    end if
                end do
            end do
        end do
    end function arithmetic_triplets
end module arithmetic_triplets

program test_arithmetic_triplets
    use arithmetic_triplets
    implicit none
    integer, parameter :: nums = [0, 1, 4, 6, 7, 10]
    integer, parameter :: diff = 3
    integer :: count

    count = arithmetic_triplets(nums, diff)
    write (*,*) "Number of arithmetic triplets:", count

    count = arithmetic_triplets([4, 5, 6, 7, 8, 9], 2)
    write (*,*) "Number of arithmetic triplets:", count
end program test_arithmetic_triplets
🌐 Data from online sources 
def count_arithmetic_triplets(nums, diff):
    count = 0
    mp = {}
    for num in nums:
        if num - diff in mp:
            count += mp[num - diff]
        mp[num] = mp.get(num, 0) + 1
    return count

The algorithm uses a hashmap to store the number of occurrences of the elements in the given array. For each element, we check if the hashmap contains the element minus the given difference (i.e., num - diff). If it does, that means we have found a valid arithmetic triplet, so we increment the count by the number of occurrences of that element minus the difference. Finally, we update the number of occurrences of the current element in the hashmap.

This algorithm has a time complexity of O(n), where n is the size of the given array, since we iterate through the array once and perform lookups, insertions, and updates on the hashmap in constant time.

🌐 Data from online sources 
int countArithmeticTriplets(vector<int> &nums, int diff) {
    int count = 0;
    unordered_map<int, int> mp;
    for (int num : nums) {
        if (mp.count(num - diff))
            count += mp[num - diff];
        mp[num]++;
    }
    return count;
}

The algorithm uses a hashmap to store the number of occurrences of the elements in the given array. For each element, we check if the hashmap contains the element minus the given difference (i.e., num - diff). If it does, that means we have found a valid arithmetic triplet, so we increment the count by the number of occurrences of that element minus the difference. Finally, we update the number of occurrences of the current element in the hashmap.

This algorithm has a time complexity of O(n), where n is the size of the given array, since we iterate through the array once and perform lookups, insertions, and updates on the hashmap in constant time.