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.
