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, 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> wrote:
> > > On Tue, Nov 22, 2011 at 11:50 PM, tech coder <[email protected]
> > >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 <[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.
>
> > > --
> > > 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 [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.
--
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.
