@Gene : Are you sure, when you pop element from stack it will not be next
smaller element to remaining elements in the array(Input)?? I think this is
not gonna work...
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.
>
--
Thanks and Regards,
Sumit Mahamuni.
-- Slow code that scales better can be faster than fast code that doesn't
scale!
-- Tough times never lasts, but tough people do.
-- I love deadlines. I like the whooshing sound they make as they fly by. -
D. Adams
--
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.
