Here is my code with logic techcoder described ...
void PushSmallerElement(int a[],int n){
stack<pair<int,int> >s;
pair<int,int>p;
int top;
for(int i=0;i<n;i++){
if(s.empty())
s.push(pair<int,int>(a[i],i));
else{
p=s.top();
while( !s.empty() && a[i]<p.first ){
s.pop();
a[p.second]=a[i];
p=s.top();
}
}
s.push(pair<int,int>(a[i],i));
}
while(!s.empty()){
p=s.top();
s.pop();
a[p.second]=0;
}
}
On Wed, Nov 23, 2011 at 3:43 PM, 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.
