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) On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage <[email protected]> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
