Urm. It's probably not the same. We could find the maximum element in the array and use the trivial approach till we reach the max_element. After that, all we need to do is to shift all the elements right of max_element to the left by 1 and place max_element at the end. But again..this isn't O(n). :-P Worst case: O(n^2).
On Sun, Mar 25, 2012 at 10:44 PM, algo bard <algo.b...@gmail.com> wrote: > http://www.geeksforgeeks.org/archives/8405 > > ^ Similar Question. > > On Mar 25, 4:49 pm, atul anand <atul.87fri...@gmail.com> wrote: > > wont work for all cases...ignore > > i will post the algo....once i fix it > > On 25 Mar 2012 17:06, "Amol Sharma" <amolsharm...@gmail.com> wrote: > > > > > > > > > > > > > > > > > @atul : it would be better for all to understand if you write the algo > > > instead of writing the code.. > > > -- > > > > > Amol Sharma > > > Third Year Student > > > Computer Science and Engineering > > > MNNIT Allahabad > > > <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99>< > http://in.linkedin.com/pub/amol-sharma/21/79b/507>< > http://www.simplyamol.blogspot.com/> > > > > > On Sun, Mar 25, 2012 at 4:51 PM, atul anand <atul.87fri...@gmail.com > >wrote: > > > > >> @shady : yes i guess this is what question says:- > > >> so acc to this below algo work , i didnt execute it but i guess it > will > > >> work > > > > >> void nextSmaller(int arr[],int n) > > >> { > > >> s1 s; > > >> int i,next,ele; > > > > >> s.top=-1; > > >> push(&s,0); > > > > >> for(i=1;i<n;i++) > > >> { > > >> next=arr[i]; > > >> if(isEmpty(&s)) > > >> { > > >> ele=pop(&s); > > >> while(arr[ele] > next) > > >> { > > >> swap(arr,ele,i); > > >> next=arr[ele]; > > >> if(isEmpty(&s)==0) > > >> { > > >> break; > > >> } > > >> ele=pop(&s); > > >> } > > >> if(ele > next) > > >> { > > >> push(&s,ele); > > >> } > > > > >> } > > > > >> push(&s,i); > > >> } > > > > >> } > > > > >> On Sun, Mar 25, 2012 at 4:36 PM, shady <sinv...@gmail.com> wrote: > > > > >>> @gene > > >>> i think for 3 4 2 you need to start from left most element, and then > > >>> make substitutions one by one. > > >>> so it will be > > >>> 3 4 2 > > >>> 2 4 3 > > >>> 2 3 4 > > > > >>> @all i googled a bit, and found that O(n) solution is possible for > it, > > >>> any idea ? > > > > >>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan < > kartik.sac...@gmail.com>wrote: > > > > >>>> +1 @saurabh...:P > > > > >>>> -- > > >>>> 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. > > > > >> -- > > >> 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. > > -- > 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.
