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.
