Pairs

Hello World!

Let’s get going with the problem Pairs on HackerRank. You may click on the title to read the problem statement. So let’s start…

We have been given N distinct numbers in the input. We need to find number of pairs that have difference K between them. The problem seems obvious and once possible brute forcing solution would be to compare each element with remaining N-1 elements and count how many of those have difference K. This would have time complexity of N². As the constraints are large, this technique might give timeout error.

Although the above is a valid solution, we can come up with something better in terms of time complexity. Let’s sort the array of N distinct numbers in ascending order. Then we would consider two pointers i = 0 and j = 1. It is given that N ≥ 2 so no need to worry about assigning values to i and j directly. Initialize a variable count = 0.

Now calculate the difference of element at j index and element at i index. If the difference is K, increment count and j. If the difference is less than K, it means that we need to increment j in order to get a larger number from the array and increase the difference towards K. If the difference is greater than K, we need to increment i in order to decrease the difference towards K. Run the loop till j reaches the end of the array.

Open for suggestions. The code for this problem in Python3 can be found here.

Suggested reading: Two Pointers Technique

Happy coding…