CODEWITHSUNDEEP
algorithm
user6439492
user6439492

Reputation:

Algorithm for max distance in elements

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??

Upvotes: 1

Views: 1386

Answers (1)

A. Sarid
A. Sarid

Reputation: 3996

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)

Upvotes: 1

Related Questions