Fastest algorithm possible to pick number pairs

Question

The question: Given N integers [N<=10^5], count the total pairs of integers that have a difference of K. [K>0 and K<1e9]. Each of the N integers will be greater than 0 and at least K away from 2^31-1 (Everything can be done with 32 bit integers).

1st line contains N & K (integers). 2nd line contains N numbers of the set. All the N numbers are assured to be distinct.

Now the question is from hackerrank. I got a solution for the question but it doesn't satisfy the time-limit for all the sample test cases. I'm not sure if its possible to use another algorithm but I'm out of ideas. Will really appreciate if someone took a bit of time to check my code and give a tip or two.

temp = input()
temp = temp.split(" ")
N = int(temp[0])
K = int(temp[1])
num_array = input()
num_array = num_array.split(" ")
diff = 0
pairs= 0
i = 0
while(i < N):
    num_array[i] = int(num_array[i])
    i += 1
while(num_array != []):    
    j = 0
    while(j < (len(num_array)-1)):
        diff = abs(num_array[j+1] - num_array[0])
        if(diff == K):
            pairs += 1
        j += 1
    del num_array[0]
    if(len(num_array) == 1):
        break
print(pairs)

Answer 1

You can do this in aproximately linear time by following the procedure:

So, O(n) solution:

1. For each number x add it to hash-set H[x]
2. For each number x check whether x-k is in H, if yes - add 1 to answer

Or by using some balanced structure (like tree-based set) in O(nlgn)

This solution bases on the assumption that integers are distinct, if they are not you need to store the number of times element has been "added to set" and instead of adding 1 to answer - add the product of H[x]*H[x+k]

So in general you take some HashMap H with "default value 0"

1. For each number x update map: H[x] = H[x]+1
2. For each number x add to answer H[x]*H[x-k] (you don't have to check whether it is in the map, because if it is not, H[x-k]=0 )

and again - solution using hash-map is O(n) and using tree-map O(nlgn)

So given set of numbesr A, and number k (solution for distinct numbers):

H=set()
ans=0
for a in A: 
  H.add(a)
for a in A: 
  if a-k in H: 
    ans+=1
print ans

or shorter

H=set(A)
ans = sum(1 for a in A if a-k in H)
print ans

Answer 2

Use a dictionary (hash map).

Step 1: Fill the dictionary D with all entries from the array. Step 2: Count occurences of all A[i] + k in the dictionary.

Dictionary<int> dict = new Dictionary<int>();
foreach (int n in num_array) do dict.Add(n);
int solitions = 0;
foreach (int n in num_Array) do 
  if dict.contains(n+k) 
    solutions += 1;

Filling a dictionary is O(1), Searching is O(1) as well. Doing it for each element in the array is O(n). This is as fast as it can get.

Sorry, you have to translate it to python, though.

EDIT: Same idea as the previous one. Sorry to post a duplicate. It's too late to remove my duplicate I guess.