Pairs with difference k

Given an array arr[] of positive integers. Find the number of pairs of integers whose difference equals a given number k.
Note: (a, b) and (b, a) are considered the same. Also, the same numbers at different indices are considered different.

Examples:

Input: arr[] = [1, 5, 3, 4, 2], k = 3
Output: 2
Explanation: There are 2 pairs with difference 3,the pairs are {1, 4} and {5, 2} 

Input: arr[] = [8, 12, 16, 4, 0, 20], k = 4
Output: 5
Explanation: There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8}, {8, 12}, {12, 16} and {16, 20}.

Constraints:
1 <= arr.size() <= 10⁶
1 <= k <= 10⁶
0 <= arr[i] <= 10⁶

Approach 01:

class Solution {
public:
    int countPairsWithDiffK(vector<int>& array, int difference) {
        unordered_map<int, int> frequencyMap;
        int pairCount = 0;

        // Calculate the frequency of each element in the array
        for (int value : array) {
            frequencyMap[value]++;
        }

        // Iterate through the array and check for pairs with the specified difference
        for (int value : array) {
            int targetValue = value + difference;
            if (frequencyMap.count(targetValue) > 0) {
                pairCount += frequencyMap[targetValue];
            }
        }

        return pairCount;
    }
};

class Solution:
    def countPairsWithDiffK(self, array, difference):
        frequencyMap = {}
        pairCount = 0

        # Calculate the frequency of each element in the array
        for value in array:
            frequencyMap[value] = frequencyMap.get(value, 0) + 1

        # Iterate through the array and check for pairs with the specified difference
        for value in array:
            targetValue = value + difference
            if targetValue in frequencyMap:
                pairCount += frequencyMap[targetValue]

        return pairCount

Time Complexity

• Frequency Map Construction:

  We iterate through the array to populate frequencyMap, which takes \(O(n)\), where n is the size of the array.

• Pair Counting:

  We then iterate through the array again to check each element for pairs with the specified difference K. Each check for the presence of targetValue in the map takes O(1) on average, resulting in another \(O(n)\) operation.

• Overall Time Complexity:

  The total time complexity is \(O(n)\).

Space Complexity

• Frequency Map:

  The unordered map frequencyMap stores the frequency of each element in the array. In the worst case, this requires \(O(n)\) space if all elements are unique.

• Auxiliary Variables:

  A few auxiliary variables are used, adding a constant extra space.

• Overall Space Complexity:

  The space complexity is \(O(n)\).