Numbers pairs problem on array

http://www.careercup.com/question?id=6229237509914624

Given N numbers , [N<=10^5] we need to count the total pairs of numbers which have a difference of K. [K>0 and K<10^9]. The solution should have as low of a computational time complexity as possible. 

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 

Explanation: 
The possible pairs are (5,3), (4,2) and (3,1).


==

O(n) time and O(n) space solution:
1. Keep a hashtable(HashSet would suffice) to keep the elements already seen while passing through array once.
2. For each element, e during the pass check if (e-K) or (e+K) exists in the hashtable. If exists then increment a count.
3. Add the scanned element in the hashtable.

public static int diffPairs(int[] A, int K)
{
 HashSet<Integer> hs = new HashSet<Integer>();
 int count =0;

 for(int i=0; i<A.length; i++)
 {
  if(hs.contains(A[i] - K))
   count++;
  if(hs.contains(A[i]+K))
   count++;

  hs.add(A[i]);
 }
 return count;
}

If we don't have the space then there is another solution with O(1) space and O(nlgn) time.

1. Sort the array
2. Keep two markers a start and end of the array.
3. Pass the array once. let diff = A[start]-A[end]
if abs(diff)== K then count ++
else if diff<K then start++;
else end--;

public static int diffPairs(int[] input, int K)
{
 input = sort(input);
 int start = 0;
 int end = input.length-1;
 int count = 0;

 while(start<=end)
 {
  if(abs(input[start]-input[end]) == K)
   count ++;
  else if(input[start]-input[end] <  K)
   start++;
  else end--; 
 }
 
 return count;
}