Thanks Amit and srikanth for pointing that out. I should have done
some analysis before posting this solution.
we can do this problem in 2 steps:
find-min-diff(arr a)
{
sort(a)
find(a, 0, min=INF, i=0, j=0)
return {min, i, j}
}
find(a, index, min, i, j)
{
if(a[index+1] - a[index] < min){
min = a[index+1] - a[index];
i= index, j= index+1
}
find(a, index+1, min, i, j)
}
run time -- sorting time + O(n)
space -- sorting complexity + O(1)
Let us discuss if we can do it without sorting the array elements.
I have one more question here , suppose we have some dynamic array
( of const size ) where insertions and removal is happening
dynamically --->
you want the 2 elements from the array having least difference. Design
a data structure for this. Less than O(n) solution appreciated.
On Jul 14, 9:27 am, Ashish Goel <[email protected]> wrote:
> count sort and then find mindiff
>
> fot (int i=1;i<n;i++)
> if (a[i]-a[i-1] <mindiff) { mindiff =a[i]-a[i-1]; ele1=a[i-1]; ele2=a[i];}
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
> On Tue, Jul 13, 2010 at 2:47 PM, Tech Id <[email protected]> wrote:
> > Construct a BST for the array - O(nlogn)
> > Traverse the tree and find a node which has
> > minimum difference with either its left or
> > right child in whole of the tree.
> > (Because the required numbers have to be
> > adjacent to each other in a sorted array). - O(n)
>
> > => Total order:O(nlogn)
>
> > --
> > 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.
