[Hackerrank] – Pairs Solution

Question: Given an array of integers, find the number of pairs of array elements that have a difference equal to the target value.

Example:

Input:
arr[ ] = {1, 2, 3, 4}
k = 1

Output: 3

Problem Statement

Let us try to simplify the problem statement first and understand the sample test case.

You are given an array of unique integers which is in any random order. Along with the array, you are also given a target value k. If you pick up any 2 integers from the array, they would form a pair and have some difference x - y.

You need to find out the number of these pairs which have a difference equal to the target difference k.

In the above case, you can see a total of 3 pairs which have the target difference of 1.

2 - 1 = 1\newline
3 - 2 = 1\newline
4 -3  = 1

Hence, the output of the above test case is 3.

Brute Force Solution

A Brute Force method to solve the problem would be that we calculate all the possible pairs and find out all the differences. So, if we have a given sample test case like:

We would find a total of 20 pairs.

We can then iterate over all these pairs and the find the difference. If the difference matches the target value, then we have a valid pair to count towards the solution. In the above case we find 3 pairs that have the target value of 2.

But, this solution will take up a lot of time just to compute all the possible combinations, and as your array size starts to grow, you will take more and more time to solve the problem.

Efficient Solution

An efficient way to solve the problem requires some reverse thought process. Instead of finding a pair, we can find the complimentary integer to an element that would make the difference equal to the target value.

(Element\ in\ array) - (Number\ to\ find) = target\ value

To understand it via an example, suppose we are given with the following input. The first element is 1.

1 - (Number to find) = 2
1 - (2) = Number to find
-1 = Number to findCode language: plaintext (plaintext)

Hence, if we are able to find -1 in the array, then we can be pretty sure that 1 forms a pair with -1 that has the target difference of 2. Since, we still need to search a number in the entire array, we need a way to speed up the search process. It is always easy to search in a sorted array than an unsorted array.

With all that thought in mind, the algorithm can hence be written as:

1. Sort the original array.
2. Iterate from the first element and calculate the number to find using the formula
   (Element\ in\ array) - (Number\ to\ find) = target\ value
3. Since the array is sorted, use binary search to find the element in the sorted array.
4. If we find the element, that means we can form a pair, and increment the result count.
5. Repeat steps 2-4 for every element of the array.
6. Return the result.

Code:

  // Helper function to search in the sorted array.
  private boolean binarySearch(int[] arr, int numberToFind) {

    int left = 0
    int right = arr.length - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == numberToFind) 
        return true;
      if (arr[mid] < numberToFind) 
        left = mid + 1;
      else 
        right = mid - 1;
    }
    return false;
  }

  public int pairs(int k, int[] arr) {

    // Sort the array
    Arrays.sort(arr);

    int result = 0;
    for (int i : arr) {
      int numberToSearch = i - k;
      if (binarySearch(arr, numberToSearch)) {
        result++;
      }
    }

    return result;
  }
Code language: Java (java)

Time Complexity: O(n * log n) [Since we are sorting the array]
Space Complexity: O(1)

You can find the code and test cases on Github.
The problem statement on HackerRank.

Video Explanation: