CODEWITHSUNDEEP
ruby-on-railsalgorithmtime-complexity
Klaus Turbo
Klaus Turbo

Reputation: 2960

Get distance of elements inside an array?

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?

Upvotes: 6

Views: 1175

Answers (3)

BufBills
BufBills

Reputation: 8113

Typically for this kinda Array related problem. If you have algorithm equal to or worse than O(n^2) you can always consider using sorting algorithm to process it. Usually takes O(lgn), then you may have a linear algorithm after that.

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

so you can:

sorted = arr.sort

Then use one loop to copmare

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

Upvotes: 2

wohlert
wohlert

Reputation: 340

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

Upvotes: 3

amit
amit

Reputation: 178521

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

Upvotes: 9

Related Questions