@piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ???
WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu <duman...@gmail.com> wrote: > @Piyush: could u plz post the link to the same? > > On Jun 22, 2:15 pm, Piyush Sinha <ecstasy.piy...@gmail.com> wrote: > > > > > > > > > This question has been discussed over here once...It was concluded > > that this can be solved in O(n) if we know there is a fixed range up > > to which the elements keep on increasing and decreasing..for example > > in an array of 12 elements, we know 3 elements keep on increasing > > monotonically, then 3 elements keep on decreasing monotonically and so > > on > > > On 6/22/11, chirag ahuja <sparkle.chi...@gmail.com> wrote: > > > > Given an array of size n wherein elements keep on increasing > > > monotonically upto a certain location after which they keep on > > > decreasing monotonically, then again keep on increasing, then > > > decreasing again and so on. Sort the array in O(n) and O(1). > > > > I didn't understand the question, any array of n elements will be like > > > this except when first there is a decrese from index 0 to a higher > > > index. Any ideas about how to solve it in given constraints?? > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > *Piyush Sinha* > > *IIIT, Allahabad* > > *+91-8792136657* > > *+91-7483122727* > > *https://www.facebook.com/profile.php?id=100000655377926*-Hide quoted text - > > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
