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.
I think the "two-pointer technique" isn't O(n), but O(n²) because of the two [nested] while loops
- what kind of an argument is that? The outer loop looks O(n), and there is an inner loop, so it will be O(n) times the complexity of the inner loop - which is in O(1): the "inner index" does not get re-initialised. \$\endgroup\$while
loop runs till the difference becomes less thank
. Wouldn't that make the complexity O(n)? \$\endgroup\$