I'm doing this HackerRank problem:
Given \$N\$ integers, count the number of pairs of integers whose difference is \$K\$.
So far, I've ended up with this code:
def countPairs(ar, n, k): ar.sort() temp = list(ar) i = 0 j = n - 1 cnt = 0 while i < n: while abs(ar[i] - temp[j]) > k and j > 0: j -= 1 if abs(ar[i] - temp[j]) == k: cnt += 1 i += 1 j = n - 1 return cnt if __name__ =='__main__': N, K = map(int, raw_input().strip().split()) A = map(int, raw_input().strip().split()) print countPairs(A, N, K)
The problem is some test cases terminated due to timeout (took more than 10 seconds).
I tried calculating the time complexity. Sorting the list in the first step of
countPairs takes \$O(n\log n)\$ and copying the list in the second step into
temp takes \$O(n)\$.
This link says that the "two-pointer technique" has \$O(n)\$ complexity. So, the overall complexity is \$O(n \log n)\$. Does anyone know how to make it run faster?
To be honest, I think the "two-pointer technique" isn't \$O(n)\$, but \$O(n^2)\$ because of the two
while loops, but I'm not sure.