Hi Friends This is an interesting problem and request you all to give a brief intro to your code before putting the code. Or you may just mention the under lying concept in the code. This will be of great help and others will find it more ready to improve by adding there approach.
Coming back to the problem an O(n) solution can exist by following the approach of building a min heap (or max heap) from an array of elements. A mean heap from an array of elements can be built by starting from middle element (all elements from mid +1 to end are them selves single element min heaps) (references available in Cormen or other books). During constructing the mean heap always track the min difference between any two elements in the so far constructed heap. At any instant if you are handling root 'a' which has left child l and right child r and aiming to build a min heap rooted at a, then the following cases arise 1. a is less than both l and r. In this case no movement of a is required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a difference z with any element under tree rooted at l such that z < x becuase l is the least element in the tree rooted at l. Similarly 'a' cannot have a difference z' with any element under tree rooted at r such that z' < r. So least of x and y is the min diff between any elements in the so far constructed min heap rooted at 'a'. 2. a is less than l but greater than r. In this case r will replace a and a need to be pushed down the its right child. While pushing 'a' down keep calculating the differences between 'a' and 'r' as long as 'a' is not pushed down to a node where it is the min element. While you keep calculating also keep track of the min diff calculated so far (say 'p'). Compare this 'p' with |a-l| and min diff between any two elements for the tree rooted at l. Least of these three will be the min diff between any 2 elements for the min head rooted at 'r' (which replaced 'a''s position. 3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r' and replace that with 'a' and push 'a' down as in case 2 (normal min heap construction algo). Thus we can continue building the min heap and at the end have the min diff between any 2 elements in the array. Just we keep tracking the min diff, we can also keep note of the 2 elements than are contributing to this min diff my adding some more steps. This idea is all based on the fact that min heap can be constructed from an array in linear time. Thanks, Sourav On Sep 27, 1:32 pm, rahul <[email protected]> wrote: > If their is no constrain on assumptions. > > 1.Sort the array. > 2. check the dif between 2 elements. > > { 99,35,45,33,88,9098,112,33455,678,3} > > sorted arrary : { } would be something. > now update the min_diff. > > another example : { 7,8,1,3,5,4} > sorted arrary : { 1,3,4,5,7,8} > min diff is 1. > > Please correct me if i missed something. > > On Mon, Sep 27, 2010 at 1:13 PM, satish <[email protected]> wrote: > > step1>construct heap using siftdown. // time complexity wil be O(n) and > > space complexity O(1). > > step2>take mindifference=a[1]. > > step3>for i=1 ,i<=n/2 do > > { find the difference of (root,root-left),(root,root->right)and > > (root->left,root->right).and maintain mindifference is the smallest > > difference of among > > three differences. > > } > > step4>return mindifference. > > > plz correct me if im wrong.... > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%[email protected]> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
