current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
stack overflow careers
Sign up ×
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other. Join them; it only takes a minute:
up vote 0 down vote favorite

I have an array A = [a1, a2, a3, a4, a5...] and I want to find two elements of the array, say A[i] and A[j] such that i is less than j and A[j]-A[i] is minimal and positive.

The runtime has to be O(nlog(n)).

Would this code do the job:

  1. First sort the array and keep track of the original index of each element (ie : the index of the element in the ORIGINAL (unsorted) array.

  2. Go through the sorted array and calculate the differences between any two successive elements that verify the initial condition that the Original Index of the bigger element is bigger than the original index of the smaller element.

  3. The answer would be the minimum value of all these differences.

Here is how this would work on an example:

A = [0, -5, 10, 1]

In this case the result should be 1 coming from the difference between A[3] and A[0].

  • sort A : newA=[-5,0,1,10]

  • since OriginalIndex(-5)>OriginalIndex(0), do not compute the difference

  • since OriginalIndex(1)>OriginalIndex(0), we compute the difference = 1

  • since OriginalIndex(10)>OriginalIndex(1), we compute the difference = 9

The result is the minimal difference, which is 1.

share|improve this question

2 Answers 2

up vote 2 down vote

Contrary to the claim made in the other post there wouldn't be any problem regarding the runtime of your algorithm. Using heapsort for example the array could be sorted in O(n log n) as given as an upper bound in your question. An additional O (n) running once along the sorted array couldn't harm this any more, so you would still stay with runtime O (n log n).

Unfortunately your answer still doesn't seem to be correct as it doesn't give the correct result.

Taking a closer look at the example given you should be able to verify that yourself. The array given in your example was: A=[0,-5,10,1]

Counting from 0 choosing indices i=2 and j=3 meets the given requirement i < j as 2 < 3. Calculating the difference A[j] - A[i] which with the chosen values comes down to A[3] - A[2] calculates to 1 - 10 = -9 which is surely less than the minimal value of 1 calculated in the example application of your algorithm.

share|improve this answer
    
Hi mikyra, I forgot to mention that the difference has to be positive. In this case it would work ? – user2205925 Mar 25 '13 at 3:48
    
If only positive values are allowed as already shown by Garys proof everything should work fine. – mikyra Mar 25 '13 at 4:10
up vote 1 down vote

Since you're minimising the distance between elements, they must be next to each other in the sorted list (if they weren't then the element in between would be a shorter distance to one of them -> contradiction). Your algorithm runs in O(nlogn) as specified so it looks fine to me.

share|improve this answer
    
I don't think the assumption two points with minimal distance will yield the correct result holds. While this would hold true if the array was sorted already if there is any index out of the normal search order it rather boils down to maximizing the distance as the more negative the number gets the more minmal the difference will be. – mikyra Mar 25 '13 at 3:40
    
Yeah, i guess i was assuming |A[j]-A[i]| and therefore not taking negative values into account. I suppose if the example was [0,1,10,-5] then the answer would be -15 but the elements would not be next to each other when sorted. – Gary Garygary Mar 25 '13 at 3:52
    
As it turns you were right with your assumption as only positive distances are allowed. – mikyra Mar 25 '13 at 4:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.