Count all distinct pairs with difference equal to K | Set 2

0 0 5 minutes read

Given an integer array arr[] and a positive integer K, the task is to count all distinct pairs with differences equal to K.

Examples:

Input: arr[ ] = {1, 5, 3, 4, 2}, K = 3
Output: 2
Explanation: There are 2 distinct 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 unique pairs with difference 4.
The pairs are {0, 4}, {4, 8}, {8, 12}, {12, 16} and {16, 20}

The naive approach and approach based on sorting and binary search are mentioned on the Set 1 of this article.

Approach: The time complexity for this problem can be reduced to have a linear complexity in average case by using hashing with the help of unordered maps as per the following idea:

For forming such unique pairs, if traversed from the smallest element, an element (say x) will form such a pair with another element having value (x+K).
When the difference K = 0 then the elements having frequency more than 1 will be able to form pairs with itself.

Follow the steps mentioned below to solve the problem:

Initialize an unordered map and push all the array elements into the map.
If the given value of K is 0:
- If the frequency of current element x is greater than 1, increment count by 1.
- Else try the same for the other elements.
If the given value of K is not 0:
- Search x + K in the map and if it is found, increment the count by 1.
- Else try for the other elements.
Return the count.

Below is the implementation of the above approach.

C++

// C++ code to implement the above approach.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find total pairs
int TotalPairs(vector<int> nums, int K)
{
    // Initializing a map
    unordered_map<int, int> mp;
    int cnt = 0;
 
    for (int i = 0; i < nums.size(); i++) {
        mp[nums[i]]++;
    }
 
    // Difference equal to zero
    if (K == 0) {
        for (auto i : mp) {
 
            // Frequency of element is
            // greater than one then
            // distinct pair is possible
            if (i.second > 1)
                cnt++;
        }
    }
 
    // Difference is not equal to zero
    else {
        for (auto i : mp) {
 
            // Frequency of element + k
            // is not zero then distinct
            // pair is possible
            if (mp.find(i.first + K)
                != mp.end()) {
                cnt++;
            }
        }
    }
    return cnt;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 8, 12, 16, 4, 0, 20 };
    int K = 4;
 
    // Function call
    int ans = TotalPairs(arr, K);
    cout << ans;
    return 0;
}

Java

// Java code to implement the above approach.
import java.io.*;
import java.util.*;
 
class GFG {
    // Function to find total pairs
    public static int TotalPairs(int nums[], int K)
    {
        // Initializing a map
        Map<Integer, Integer> mp
            = new HashMap<Integer, Integer>();
        int cnt = 0;
 
        for (int i = 0; i < nums.length; i++) {
            if (mp.get(nums[i]) != null)
                mp.put(nums[i], mp.get(nums[i]) + 1);
            else
                mp.put(nums[i], 1);
        }
 
        // Difference equal to zero
        if (K == 0) {
            for (Map.Entry<Integer, Integer> it :
                 mp.entrySet()) {
 
                // Frequency of element is
                // greater than one then
                // distinct pair is possible
                if (it.getValue() > 1)
                    cnt++;
            }
        }
 
        // Difference is not equal to zero
        else {
            for (Map.Entry<Integer, Integer> it :
                 mp.entrySet()) {
 
                // Frequency of element + k
                // is not zero then distinct
                // pair is possible
                if (mp.get(it.getKey() + K) != null) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
    public static void main(String[] args)
    {
        int arr[] = { 8, 12, 16, 4, 0, 20 };
        int K = 4;
 
        // Function call
        int ans = TotalPairs(arr, K);
        System.out.print(ans);
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python3 program for above approach
 
# function to find total pairs
def TotalPairs(nums, K):
   
    # Initializing a map or dictionary
    mp = dict()
    cnt = 0
    for i in range(len(nums)):
        if nums[i] in mp:
            mp[nums[i]] += 1
        else:
            mp[nums[i]] = 1
 
    # Difference equal to zero
    if K == 0:
        for i in mp:
            # Frequency of element is
            # greater than one then
            # distinct pair is possible
            if mp[i] > 1:
                cnt += 1
    # Difference is not equal to zero
    else:
        for i in mp:
            # Frequency of element + k
            # is not zero then distinct
            #pair is possible
            if i + K in mp:
                cnt += 1
 
    return cnt
 
# Driver Code
arr = [8, 12, 16, 4, 0, 20]
K = 4
 
# Function call
ans = TotalPairs(arr, K)
print(ans)
 
# This code is contributed by phasing17

C#

// C# code to implement the above approach.
 
using System;
using System.Collections.Generic;
 
public class GFG {
  public static int TotalPairs(int[] nums, int K)
  {
    // Initializing a map
    Dictionary<int, int> mp
      = new Dictionary<int, int>();
 
    int cnt = 0;
 
    for (int i = 0; i < nums.Length; i++) {
      if (mp.ContainsKey(nums[i]))
        mp[nums[i]] += 1;
      else
        mp[nums[i]] = 1;
    }
 
    // Difference equal to zero
    if (K == 0) {
      foreach(KeyValuePair<int, int> it in mp)
      {
 
        // Frequency of element is
        // greater than one then
        // distinct pair is possible
        if (it.Value > 1)
          cnt++;
      }
    }
 
    // Difference is not equal to zero
    else {
      foreach(KeyValuePair<int, int> it in mp)
      {
 
        // Frequency of element + k
        // is not zero then distinct
        // pair is possible
        if (mp.ContainsKey(it.Key + K)) {
          cnt++;
        }
      }
    }
    return cnt;
  }
 
  public static void Main(string[] args)
  {
    int[] arr = { 8, 12, 16, 4, 0, 20 };
    int K = 4;
 
    // Function call
    int ans = TotalPairs(arr, K);
    Console.Write(ans);
  }
}
 
// This code is contributed by phasing17

Javascript

<script>// JavaScript program for the above approach
 
// function to find total pairs
function TotalPairs(nums, K)
{
    // Initializing a map or dictionary
    var mp = {};
    var cnt = 0;
    for (var i = 0; i < nums.length; i++) {
        if (mp.hasOwnProperty(nums[i]))
            mp[nums[i]] += 1;
        else
            mp[nums[i]] = 1;
    }
 
    // Difference equal to zero
    if (K == 0) {
        for (const i of Object.keys(mp)) {
            // Frequency of element is
            // greater than one then
            // distinct pair is possible
            console.log(i, mp[i], cnt);
            if (mp[i] > 1)
                cnt += 1;
        }
    }
 
    // Difference is not equal to zero
    else {
        for (const i of Object.keys(mp)) {
            // Frequency of element + k
            // is not zero then distinct
            // pair is possible\
            if (mp.hasOwnProperty(parseInt(i) + K))
            {
                cnt += 1;
            }
        }
    }
    return cnt;
}
// Driver Code
var arr = [ 8, 12, 16, 4, 0, 20 ];
var K = 4;
 
// Function call
// var ans = TotalPairs(arr, K);
document.write(TotalPairs(arr, K));
 
// This code is contributed by phasing17
</script>

Output

Time Complexity: O(N) [In average case, because the average case time complexity of unordered map is O(1)]Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!