@Gene - nice, correct and elegant algorithm. On Wed, Nov 23, 2011 at 9:33 PM, Ankur Garg <ankurga...@gmail.com> wrote:
> @Gene > > Your algo is also right...Just that I followed techcoders logic and coded > the same...pair I used to map the index of the element ..But urs working > fine too :) > > > On Wed, Nov 23, 2011 at 7:04 PM, Gene <gene.ress...@gmail.com> wrote: > >> Sorry I forgot to initialize p. It's fixed below. >> >> On Nov 23, 6:59 am, Gene <gene.ress...@gmail.com> wrote: >> > Thanks. Maybe I'm not reading correctly, but tech coder's algorithm >> > doesn't mention anything about pairs, which are necessary to obtain >> > O(n). This is what I meant by "almost." >> > >> > In reverse order, you don't need the pairs. Its simpler. >> > >> > In a subroutine like yours, >> > >> > void find_smaller_to_right(int *a, int n) >> > { >> > int i, in, p=0, stk[n]; // C99 var length array >> > for (i = n - 1; i >= 0; i--) { >> > in = a[i]; >> > while (p > 0 && stk[p - 1] >= in) p--; // pop >> > a[i] = (p > 0) ? stk[p - 1] : 0; >> > stk[p++] = in; // push >> > } >> > >> > } >> > >> > On Nov 23, 5:13 am, Ankur Garg <ankurga...@gmail.com> wrote: >> > >> > >> > >> > > Solution given by tech coder is fine and is working .. I coded it and >> its >> > > working perfectly using stack >> > >> > > On Wed, Nov 23, 2011 at 2:50 PM, Gene <gene.ress...@gmail.com> wrote: >> > > > It's a nice problem, and this solution is almost right. >> > >> > > > Process the input in _reverse_ order, which means we'll also >> generate >> > > > output in reverse order. >> > >> > > > The invariant is that the stack is a sorted list - highest value on >> > > > top - of the strictly descending subsequence of elements seen so far >> > > > in reverse. >> > >> > > > So when we get a new input, we want to search backward through the >> > > > stack to find the first smaller element. This is handy however, >> > > > because the new input also means that when we search past an >> element, >> > > > it's too big to maintain the invariant, so it must be popped! We >> can >> > > > both find the output value and update the stack at the same time: >> > >> > > > stack = empty >> > > > for next input I in _reverse order_ >> > > > while stack not empty and top of stack is >= I >> > > > pop and throw away top of stack >> > > > if stack is empty, output is zero >> > > > else output top of stack >> > > > push I >> > > > end >> > >> > > > Since each item is pushed and popped no more than once, this is >> O(n). >> > >> > > > Here's your example: >> > >> > > > #include <stdio.h> >> > >> > > > int main(void) >> > > > { >> > > > int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 }; >> > > > int n = sizeof in / sizeof *in - 1; >> > > > int out[100], stk[100], p = 0, i; >> > >> > > > for (i = n - 1; i >= 0; i--) { >> > > > while (p && stk[p - 1] >= in[i]) p--; >> > > > out[i] = (p > 0) ? stk[p - 1] : 0; >> > > > stk[p++] = in[i]; >> > > > } >> > > > for (i = 0; i < n; i++) printf(" %d", out[i]); >> > > > printf("\n"); >> > > > return 0; >> > > > } >> > >> > > > On Nov 22, 2:20 pm, 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. >> >> -- >> 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. > -- Nitin Garg "Personality can open doors, but only Character can keep them open" -- 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.