ealeon - 8 months ago 31

Python Question

`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:

- Sort the list :
`O(n * log(n))`

- 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.