This content originally appeared on DEV Community and was authored by Phoenix
Problem Link - Count Pairs
Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.
The value of |x| is defined as:
x if x >= 0.
-x if x < 0.
Example 1:
Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
Example 2:
Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.
Naive Approach
- find all possible pairs that has the absolute difference of k
- intialize a counter that stores total count of all pairs
- for each element in the array, check for another element in the rest of array that acheives the absolute difference of k
Code
int countKDifference(vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(abs(nums[i] - nums[j]) == k)
{
count++;
}
}
}
return count;
}
Optimal Approach
Create a HashMap for Frequencies:
- First, declare a hashmap (or dictionary) to store the frequencies of each element in the array. The element will be the key, and its frequency (i.e., how many times it appears in the array) will be the value.
Populate the HashMap:
- Traverse the array once, and for each element, update its frequency in the hashmap. If the element already exists in the hashmap, increment its frequency. Otherwise, insert it with an initial frequency of 1.
Find Valid Pairs:
- Traverse the array again. For each element arr[i]:
- Calculate two target values: k + arr[i] and arr[i] - k.
- For each of these two values, check if it exists in the hashmap. If it does, this means that the current element forms a valid pair with the element that has the calculated value.
- The number of valid pairs for the current element will be the frequency of the found element (because one element can pair with multiple instances of another).
- Add the frequency of the matching element to the count of valid pairs.
Avoid Double Counting
- Since pairs (i, j) and (j, i) are counted twice in the above approach, we are counting each pair twice. Therefore, once all pairs have been counted, divide the total count by 2 to get the final result.
Code
int countKDifference(vector<int>& nums, int k) {
int n=nums.size();
map<int,int> mp;
int count=0;
for(int i=0;i<n;i++){
mp[nums[i]]++;
}
for(int i=0;i<n;i++){
int t1=nums[i]-k;
int t2=nums[i]+k;
if(mp.find(t1)!=mp.end()){
count+=1;
}
if(mp.find(t2)!=mp.end()){
count+=1;
}
}
return count/2;
}
Note if we are aksed to calcuate distinct pairs, instead of adding frequencies of target element to the count variable, just add 1
This content originally appeared on DEV Community and was authored by Phoenix
Phoenix | Sciencx (2024-09-21T16:08:59+00:00) Count Number of Pairs With Absolute Difference K. Retrieved from https://www.scien.cx/2024/09/21/count-number-of-pairs-with-absolute-difference-k/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.