Pairs With Difference Of K – In Java, C++ And Python

TABLE OF CONTENT
Problem : Pairs with difference of K
How to approach the solution?
Test Cases
Solution in Java
Solution in C++
Solution in Python

Problem : Pairs with difference of K

You are given an integer array and the number K. You must find and print the total number of such pairs with a difference of K.

Take the absolute difference between the array's elements.

Format of Input:

The first line of input comprises an integer indicating the array's size. It will be denoted by the symbol n.
The following line contains n space-separated numbers indicating the array's elements' values.
The next line provides an integer indicating the value of K.

Format of Output:

The output's first and only line contains a count of all pairs with an absolute difference of K.

Constraints :

0 <= n <= 10^4
Time Limit: 1 sec

Sample Input 1 :

4 
5 1 2 4
3

Sample Output 1 :

Sample Input 2 :

4
4 4 4 4 
0

Sample Output 2 :

How to approach the solution?

The naive approach to this problem would be to run a double nested loop and check every pair for their absolute difference. If it’s equal to ‘k’, we print it else we move to the next iteration.

The double nested loop will look like this:

for(i <- 0; i < arr.size() - 1; i <- i + 1):
     for(j <- i + 1; j < arr.size(); j <- j + 1):
          if(absolute difference of arr[i] and arr[k] is equal to k):
               printPair();

The time complexity of this method is O(n²) because of the double nested loop and the space complexity is O(1) since we are not using any extra space.

We can improve the time complexity to O(n) at the cost of some extra space.

The idea is that in the naive approach, we are checking every possible pair that can be formed but we don’t have to do that.

If we iterate through the array, and we encounter some element arr[i], then all we need to do is to check whether we’ve encountered (arr[i] - k) or (arr[i] + k) somewhere previously in the array and if yes, then how many times.

Ideally, we would want to access this information in O(1) time. For this, we can use a HashMap.

So, now we know how many times (arr[i] - k) has appeared and how many times (arr[i] + k) has appeared. Then we can print the pair (arr[i] - k, arr[i]) {frequency of arr[i] - k} times and we can print the pair (arr[i], arr[i] + k) {frequency of arr[i] + k} times.

We also need to look out for a few things -

Think about what will happen if k is 0. Then (arr[i] + k) will be equal to (arr[i] - k) and we will print our pairs twice! Obviously we don’t want that to happen. So we need to add an extra check for this special case.

The pseudo-code for this approach -

function pairsWithDifferenceK(arr,k):
  HashMap(integer,integer) frequencyMap
  for element in arr:
    a <- element - k
    b <- element + k
    if(frequencyMap contains the key ‘a’):
      //print pair frequencyMap[a] times
    if(k != 0 and frequencyMap contains the key ‘b’):
      //print pair frequencyMap[b] times
    //frequencyMap[element] is initially 0
    frequencyMap[element] <- frequencyMap[element] + 1

Test Cases : Pairs with difference of K

Input - Test Case #1

4
5 1 2 4
3

Input - Test Case #2

4
4 4 4 4
0

Input - Test Case #3

4
2 4 6 8
2

Output - Test Case #1

Output - Test Case #2

Output - Test Case #3

Solution in Java : Pairs with difference of K

We create a package named PairsWithDiffK. Inside the package we create two class files named Main.java and Solution.java.

In file Main.java we write our main method -

package PairsWithDiffK;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int arr[] = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int k = Integer.parseInt(br.readLine());
		System.out.println(Solution.getPairsWithDifferenceK(arr, k));
	}

}

In file Solution.java, we write our solution for Java -

package PairsWithDiffK;

import java.util.HashMap;
public class Solution {
    
    public static int getPairsWithDifferenceK(int arr[], int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int pairCount = 0;
        for(int i : arr){
            int p1 = i + k;
            boolean flag = false;
            if(i == p1) {
                flag = true;
            }
            if(map.containsKey(p1)){
                pairCount += map.get(p1);
            }
            int p2 = i - k;
            if(map.containsKey(p2) && !flag){
                pairCount += map.get(p2);
            }
            if(map.containsKey(i)){
                map.put(i, map.get(i) + 1);
            }
            else{ 
                map.put(i, 1);
            }
        } 
        return pairCount;
    }
}

Solution in C++ : Pairs with difference of K

We create a folder named "PairsWithDiffK". Inside this folder we create two files named Main.cpp and PairsWithDifferenceK.h

Inside file Main.cpp we write our C++ main method for this problem.

#include <iostream>
using namespace std;

#include "PairsWithDifferenceK.h"

int main() {
    int n;
    cin >> n;

    int *input = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> input[i];
    }

    int k;
    cin >> k;

    cout << getPairsWithDifferenceK(input, n, k);

    delete[] input;
}

Inside file PairsWithDifferenceK.h we write our C++ solution.

#include <unordered_map> 
int getPairsWithDifferenceK(int *arr, int n, int k) { 
    unordered_map<int, int> freq; 
    
    int pairCount = 0;
    
    for (int i = 0; i < n; ++i) { 
        int complement = arr[i] + k; 
        pairCount += freq[complement]; 
        
        if (k != 0) {
            complement = arr[i] - k; 
            pairCount += freq[complement]; 
        } 
        ++freq[arr[i]]; 
    }
    
    return pairCount; 
}

Solution in Python : Pairs with difference of K

Inside file PairsWithDiffK.py we write our Python solution to this problem.

def printPairDiffK(l, k):
    pairCount=0
    m = {}

    for num in l:
        if num+k in m:
            pairCount += m[num+k]
        if k!=0 and num-k in m:
            pairCount += m[num-k]
        
        # Update map
        if num in m:
            m[num] += 1
        else:
            m[num] = 1

    return pairCount

#Main method
n=int (input())
l=list(int(i) for i in input().strip().split(' '))
k=int (input())
print(printPairDiffK(l, k))

Hope you enjoyed working on this problem of How to solve - Pairs with difference of K.

Pairs with difference of K – in Java, C++ and Python