This problem cannot be solved in less than O(nlgn) time with O(1) space. The Element Distinctness Problem has a proven lower bound of Omega(nlgn). If the least difference problem could be solved in O(n) then we can reduce the ED Problem to Least Difference problem and solve it in O(n) time. This contradicts the lower bound. http://en.wikipedia.org/wiki/Element_distinctness_problem
We can use extra space & do counting sort but even that will not be O(size of array) but actually O(max value in the array). On Jul 12, 5:51 am, ankur aggarwal <[email protected]> wrote: > order nlogn is trivial .. > any thing better ?? > > On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg <[email protected]>wrote: > > > > > 2 6 3 7 > > check for this > > > On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar > > <[email protected]>wrote: > > >> traverse array with 2 elements keeping track of 2 min elements. time > >> O(n) space O(1) > > >> On Jul 11, 9:34 pm, Amit Jaspal <[email protected]> wrote: > >> > Constraint - O(n) > > >> > On Sun, Jul 11, 2010 at 9:24 AM, amit <[email protected]> wrote: > >> > > Given an array of size n.find 2 numbers from array whose difference is > >> > > least. > > >> > > -- > >> > > 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]> > >> <algogeeks%[email protected]<algogeeks%[email protected]> > > >> > > . > >> > > For more options, visit this group at > >> > >http://groups.google.com/group/algogeeks?hl=en. > > >> > -- > >> > Amit Jaspal > >> > Btech IT IIIT- Allahabad > > >> -- > >> 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]<algogeeks%[email protected]> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > With Regards > > Ankur Aggarwal -- 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.
