Home Arrays [Hackerrank] – Pairs Solution

[Hackerrank] – Pairs Solution

by nikoo28
0 comment

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.

First sample test case {1,2,3,4} with k=1
Fig: Sample test case #1

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:

sample test case {1,5,3,4,2} with k=2
Fig: Sample test case #2

We would find a total of 20 pairs.

fig showing all 20 possible pairs
Fig: Showing all 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.

sample test case {1,5,3,4,2} with k=2
Fig: Sample test case #2
1 - (Number to find) = 2 1 - (2) = Number to find -1 = Number to find

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; }

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:

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More