1

enter image description here

I have found a solution that you find the max and min element in the array which can be done by one loop and will take only n number of runs and then subtract them to find the max distance. Is my solution right?? Is there any better solution than this??

Improve this question
4
  • 1
    Yes, your solution is great, but it is for an entirely different problem: you are looking for the max difference, while they are looking for a min difference. Commented Sep 17, 2016 at 8:29
  • How should anyone be able to rate your improvements when you do not post the (pseudo-)code for it? Commented Sep 17, 2016 at 8:33
  • are the elements sorted? Commented Sep 17, 2016 at 8:35
  • an easy way to do it, 1- use quick sort to sort the elements, 2- the min distance is A[1] - A[0] but make sure that the elements should be at least 2 elements Commented Sep 17, 2016 at 8:43

1 Answer 1

Reset to default
1

Maximum Distance

For maximum distance your solution is right. There is no better solution as you must go over all elements in the array. Time complexity will be O(n).

Pseudo-Code:

MaxDistance(A) min = max = A[0] for i=1 to n-1 if A[i] < min min = A[i] if A[i] > max max = A[i] return (max-min)

Minimum Distance

The pseudo code in your question is for finding the minimum distance between any pair in the array. A more efficient solution would be:

  1. Sort the array A in ascending order. O(nlogn)
  2. Iterate over the sorted array and compare all adjacent pairs while keeping track of the minimum distance. O(n)

Pseudo-Code:

MinDistance(A) sort(A) min_dist = infinity for i=1 to n-1 dist = A[i]-A[i-1] if (min_dist > dist) min_dist = dist return min_dist

Total time complexity: O(nlogn)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments