Get distance from elements inside an array?

Question

I am struggling with a fairly simple task that has an array of non-negative integers where I need to return the closest distance.

Array: arr = [8, 24, 3, 20, 1, 17]

Solution: 2 , arr[2]-arr[4]

Well, I managed to write a solution O (n ^ 2), which is clearly not enough.

 def smallest_distance(a) result = nil a.each_with_index do |item1, index1| a.each_with_index do |item2, index2| next if index1 == index2 temp = (item1 - item2) >= 0 ? item1 - item2 : item2 - item1 result = temp if result.nil? || temp < result end end result end 

Any ideas on how to improve this?

Answer 1

The solution is to sort the array and then repeat it. Now you only need to check the candidates that are nearby (arr[i],arr[i+1]) , and not every pair of elements.

This runs in O(NlogN) .

Note that this generalization is the Element Distinctness Problem , so if you are interested in the worst performance, you cannot achieve better than O(NlogN) .

Answer 2

The solution that amit posted is correctly n*log(n) time, which is the fastest time that a solution can be found. The ruby ​​code to solve it will look something like this:

 def smallest_distance(a) sorted = array.sort shortest = 999999 # arbitrary large value for i in 0..sorted.length comparison = sorted[i+1] - sorted[i] if sorted[i+1] != nil if comparison < shortest shortest = comparison end end return shortest end 

Answer 3

Usually for this task related to an array. If you have an algorithm equal to or worse than O (n ^ 2), you can always use a sorting algorithm to process it. Usually takes O (lgn), after that you can have a linear algorithm.

For this problem you can sort this array. Then just compare the adjacent elements for one loop. The complexity of the final result time is O (n logn), which is better than your original idea.

so you can:

 sorted = arr.sort 

Then use one loop for copmare

 arr[i] with ar[i+1] from i = 0 ~ len-1