We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges...
On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava < richi.sankalp1...@gmail.com> wrote: > @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. > > -- 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.
