Interviewstreet Challenge: Pairs

Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4e14b83d5fd12

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9 span="span">

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:3

Analysis
All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

The array contains 1,00,000 numbers and we need to find the pairs of numbers whose difference is K. There is a clue here that if the numbers are not sorted, we are only left with Brute-Force approach .
That means we need to check each number with every other number to see if they make a pair. This proves costly and we would run out of 5 seconds.
So one of the simplest solution is to sort the array using any inbuilt sort method. Now apply a modified version of binary search. So take each number 'x' and do a binary search for (x+k). If its found they make a pair. Now take the next number in the sorted array and so on.

Solution