K-Diff Pairs In An Array

Lecture 59 :- K-Diff Pairs In An Array

K-Diff Pairs in an array is a problem where you are given an integer array and an integer k. The task is to find the number of unique pairs (i, j) in the array such that the absolute difference between the elements at indices i and j is equal to k.

For example, given the array [3, 1, 4, 1, 5] and k = 2, the pairs with a difference of 2 are (3, 1) and (5, 3), so the output would be 2.

To solve this problem efficiently, we can use a hash map to keep track of the frequencies of each element in the array. Then, we can iterate through the array and for each element num, check if num + k or num - k is present in the hash map. If either of them exists and the frequency of the other element is greater than zero, we have found a valid pair.

Here's the C++ code to find the number of K-Diff pairs in an array:

cppCopy code

#include <iostream> #include <unordered_map> #include <vector> int findPairs(std::vector<int>& nums, int k) {    if (k < 0) return 0; // k cannot be negative for absolute difference    std::unordered_map<int, int> freqMap;    int count = 0;    // Count the frequency of each element in the array    for (int num : nums) {        freqMap[num]++;    }    for (auto& entry : freqMap) {        int num = entry.first;        int frequency = entry.second;        if ((k == 0 && frequency > 1) || (k > 0 && freqMap.count(num + k))) {            count++;        }    }    return count; } int main() {    std::vector<int> nums = {3, 1, 4, 1, 5};    int k = 2;    int pairsCount = findPairs(nums, k);    std::cout << "Number of K-Diff pairs: " << pairsCount << std::endl;    return 0; }

Example Output:

mathematicaCopy code

Number of K-Diff pairs: 2

In this code, the findPairs function calculates the number of K-Diff pairs using a hash map to store the frequencies of the elements. The time complexity of this approach is O(n), where n is the number of elements in the array, as we make a single pass through the array to build the hash map and count the pairs.