Get distance of elements inside an array?

Question

I'm struggling with a rather easy task which 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]

Sor far, I've only managed to write a O(n^2) solution, which is obviously not good 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 iterate it. You now only need to check for candidates that are adjacent (arr[i],arr[i+1]), and not every pair of elements.

This runs in O(NlogN).

Note that this is a generalization of Element Distinctness Problem, so if you are interested in worst case 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 that amount of time that a solution could be found. The ruby code for his solution will look something along of the lines of 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