One way could be sorting the array and also storing the original index along with that. After that we can search linearly in the array.
On Nov 23, 5:40 am, Anup Ghatage <ghat...@gmail.com> wrote: > What do you mean by " if this number is less than elements stored in > stack " > There have be N comparisons in the worst case. And that way, you have to do > it for every element. > So it will be governed by O(n^2) > > > > > > > > > > On Wed, Nov 23, 2011 at 12:50 AM, Aamir Khan <ak4u2...@gmail.com> wrote: > > > On Tue, Nov 22, 2011 at 11:50 PM, tech coder > > <techcoderonw...@gmail.com>wrote: > > >> here is an O(n) approach using a stack. > > >> problem can be stated as " find the 1st smaller element on the right. > > >> put the first element in stack. > >> take next element suppose "num" if this number is less than elements > >> stored in stack, pop those elements , for these pooped elements num will > >> be the required number. > >> put the the element (num) in stack. > > >> repeat this. > > >> at last the elements which are in next , they will have 0 (valaue) > > >> @techcoder : If the numbers are not in sorted order, What benefit the > > stack would provide ? So, are you storing the numbers in sorted order > > inside the stack ? > > > I can think of this solution : > > > Maintain a stack in which the elements will be stored in sorted order. Get > > a new element from array and lets call this number as m. Push m into the > > stack. Now, find all elements which are <= (m-1) using binary search. Pop > > out all these elements and assign the value m in the output array. Elements > > remaining at the end will have the value 0. > > > I am not sure about the complexity of this algorithm... > > >> On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage <ghat...@gmail.com> wrote: > > >>> I can't think of a better than O(n^2) solution for this.. > >>> Any one got anything better? > > >>> On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta <ankuj2...@gmail.com>wrote: > > >>>> Input: A unsorted array of size n. > >>>> Output: An array of size n. > > >>>> Relationship: > > >>>> > elements of input array and output array have 1:1 correspondence. > >>>> > output[i] is equal to the input[j] (j>i) which is smaller than > >>>> input[i] and jth is nearest to ith ( i.e. first element which is > >>>> smaller). > >>>> > If no such element exists for Input[i] then output[i]=0. > > >>>> Eg. > >>>> Input: 1 5 7 6 3 16 29 2 7 > >>>> Output: 0 3 6 3 2 2 2 0 0 > > >>>> -- > >>>> 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. > > >>> -- > >>> Anup Ghatage > > >>> -- > >>> 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. > > >> -- > >> * > > >> Regards* > >> *"The Coder"* > > >> *"Life is a Game. The more u play, the more u win, the more u win , the > >> more successfully u play"* > > >> -- > >> 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. > > > -- > > Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee > > > -- > > 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. > > -- > Anup Ghatage -- 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.
