ealeon ealeon - 5 months ago 19
Python Question

Python Algorithm: search in a list which difference is equal to k

number = [5,1,5,3,4]
k = 2


return the count which the difference is equal to k

cnt = 0
for i in nums:
for j in nums:
if i != j:
if i-j == k:
cnt += 1
return cnt


You can solve by O(N^2)

Can it be done in a faster way in terms of complexity?

it should return 3 because there are three cases which the difference is equal 2

5-3=2, 5-3=2, 3-1=2

Answer

There is a simple O(n * log(n)) solution with constant memory usage:

  1. Sort the list : O(n * log(n))
  2. For each element k in the sorted list, search for k + 2 in the list using binary search: <count of elements which is n> * O(log(n))

Hence overall complexity is O(n * log(n)).

Note that step 2 above can be made into a O(n) complexity using two pointers.