Number Of Arithmetic Triplets - Leetcode Solution

Problem Statement:

Given an array of n integers arr[], count the number of unique triplets in the array such that arr[i]+arr[j]=2*arr[k] (i<j<k).

Example:

Input: [1, 2, 3, 4, 6, 8, 9, 12, 15] Output: 4 Explanation: There are 4 triplets: (1, 2, 3), (1, 3, 5), (2, 4, 6), (3, 6, 9).

Solution Approach:

• We will create a hash map.
• We will iterate through the array arr[], and create a hash map H where key is the value of arr[i]/2 and value is the count of values equal to arr[i]/2 in the array up to the ith index.
• We will also keep track of a variable count, which will keep track of the number of arithmetic triplets found so far.
• For each i, we will iterate through all the values j less than i, and check if the sum arr[i]+arr[j] is in the hash map H.
• If it is, then the number of arithmetic triplets that can be formed from i and j is the value stored in the hash map for key (arr[i]+arr[j])/2, and we add this count to the variable count.
• At the end, we return the variable count as our answer.

Implementation:

class Solution { public: int numberOfArithmeticSlices(vector<int>& arr) { int n=arr.size(); int count=0; unordered_map<int,int> H; for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ int sum=arr[i]+arr[j]; if(H.find(sum/2)!=H.end()){ count+=H[sum/2]; } } H[arr[i]]++; } return count; } };

Time Complexity: O(n^2) Space Complexity: O(n)

In the worst case, we will iterate through all values of i and j, so the time complexity of the above code is O(n^2). The space complexity is also O(n), due to the hash map used.

1