Check distance between all elements in a list of numbers in O(n*lg(n))

Question

I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in a list X have distance greater or equal to k from each other, and I have to show that the worst case complexity of this algorithm is O(n*lg(n)).

When I think at algorithms that have to run in at most n*lg(n) time asymptotically, I think immediately about merge sort, which is exactly the divide and conquer algorithm that I used. Are my functions are correct or not?

---

Before this exercise, I had already one, where I had to create another divide and conquer function to check if there are duplicates in a list. This function should also run in O(n*lg(n)).

This is my function check_duplicates, which uses again the merge sort algorithm (I am not posting the code of the merge sort algorithm, because it's a typical merge sort. If you want me to post it, just ask!):

def check_duplicate(X):
 S = merge_sort(X) # O(n*lg(n))
 for i in range(0, len(S) - 1): # O(n)
 if S[i] == S[i + 1]:
 return True
 return False

My first questions are: Is it correct, and does it run in O(n*lg(n)) time?

---

Now, I pass to the real problem, my second function, which (as I said) should check that the distance between each element in a list is greater or equal than a constant k. For this check_distance function, I used the check_duplicate function above, to ensure that are no duplicates, otherwise it returns immediately false.

Now, my main reasoning was again to sort the list. Once the list is sorted, the a_{i + 1} element will always be greater or equal than a_i, therefore, for all a_i in X, a_i <= a_{i + 1} <= a_{i + 2}, etc.

Now, again, for all a_i in X, if I sum a_i + k, and this is less or equal than a_{i + 1}, then the distance between all elements should be>= k.

Am I correct?

def check_distance(X, k):
 if check_duplicate(X): # n*lg(n)
 return False
 else: # no duplicate values
 A = merge_sort(X)
 for i in range(len(A) - 1):
 if A[i] + k > A[i + 1]:
 return False
 return True

If I am not correct, is there a better approach?

• Pieter B: The check_duplicate is not needed. And your code will break on 1 set element. Also what about negative k ?
• 9000: «all numbers in a list X have distance greater or equal to k from each other» is a bit unclear to me. What is "each other" — just neighbors or an arbitrary other number in the list? For the former, an O(N) solution is obvious, for the latter, an O(N log N) solution with sorting is also obvious.
• Stefan Pochmann: @9000 He already has both of those solutions, and both the O(n log n) requirement and him sorting make rather clear that it's not about neighbors in the original order.
• 9000: @StefanPochmann: While I understand that everything hints to a sort-oriented solution, I'd prefer a stricter problem statement. For instance, the 'divide and conquer' hint is not entirely applicable to sorting solution: quicksort does classic divide and conquer, merge sort works a bit differently (and BTW merge sort is always O(N log N), quicksort isn't).
• chux: It would be a more fun problem if the distance involved a (.x, .y) for each element.

Answer 1

I guess you don't need this anymore, but since I realized gnasher's bump only after thinking about this, I'll leave some imho nicer code here anyway:

def check_distance(X, k):
 A = merge_sort(X)
 return all(b-a >= k for a, b in zip(A, A[1:]))

I'm interested in the teacher's solution. Did he just have this braindead sort and sweep in mind, or something more interesting?

Answer 2

The obvious solution is to sort the array in O (n log n), and then the elements can be checked sequentially in O (n). I wonder what is going on in the teachers mind when he asks for a "divide and conquer" algorithm.

Answer 3

check_duplicate is redundant. The list must not be sorted because sorting rearanges elements.

Calculate the difference between two consecutive elements and compare the value against k.

def check_distance(x, k):
 l = len(x)
 if l in [0,1]:
 return False
 for i in range(l-1):
 if x[i+1] - x[i] < k:
 return False
 return True

Using recursion,

def check_dist(x,k):
 l = len(x)
 if l == 2:
 return x[1] - x[0] >= k
 if l in (0,1):
 return False
 return x[1] - x[0] >= k and check_dist(x[1:],k)

• Nizam Mohamed: I wonder if yours is divide and conquer.
• Nizam Mohamed: You are iterating over result of the sort. It doesn't matter if it's merge or bubble, it's a sorting. If x2 => x1+k it's already sorted. If x = 5,2 and k = 1,2,3 your code gives True, because you sort. For the given result k should be k >= -3

Answer 4

I would use the first half of a counting sort.

def check_distance(arr,k): 
 count_sort = [0] * (max(arr)+1)
 smallest = arr[0]
 # Run half of a counting sort. 
 # We don't need to output the soreted array 
 for i in arr:
 count_sort[i] += 1 
 if i < smallest: smallest = i
 # now we have a count sorted array by index.
 # and we know where the first number!=0 is. 
 seen = smallest
 # the index distance between non zero values is the value distance 
 for n,z in enumerate(count_sort[smallest+1:]): # One pass - smallest 
 if z != 0: 
 dist = n-seen
 if dist < k: return False
 seen = n
 return True