i guess it can be done by modifying solution on
http://www.geeksforgeeks.org/archives/8405
my prev soln was based on the same..
instead of adding value to the stack...add index of that element.
in below code , line in bold are added
void nextSmaller(int arr[],int n)
{
s1 s;
int i,next,ele;
s.top=-1;
push(&s,0);
for(i=1;i<n;i++)
{
next= i ;
if(isEmpty(&s))
{
idx=pop(&s);
while(arr[idx] > arr[next])
{*
swap(arr,idx,i);* // swap value at index ele
end i
* next=idx; // *current value is at
index idx* , *this is to track the current element*
*
if(isEmpty(&s)==0)
{
break;
}
idx=pop(&s);
}
if(arr[idx] < arr[next])
{
push(&s,idx);
}
}
push(&s,i);
}
}
On Sun, Mar 25, 2012 at 10:39 PM, algo bard <[email protected]> wrote:
> http://www.geeksforgeeks.org/archives/8405
>
> ^ Similar question.
>
>
> On Sun, Mar 25, 2012 at 5:19 PM, atul anand <[email protected]>wrote:
>
>> wont work for all cases...ignore
>> i will post the algo....once i fix it
>> On 25 Mar 2012 17:06, "Amol Sharma" <[email protected]> wrote:
>>
>>> @atul : it would be better for all to understand if you write the algo
>>> instead of writing the code..
>>> --
>>>
>>>
>>> Amol Sharma
>>> Third Year Student
>>> Computer Science and Engineering
>>> MNNIT Allahabad
>>> <http://gplus.to/amolsharma99>
>>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Sun, Mar 25, 2012 at 4:51 PM, atul anand <[email protected]>wrote:
>>>
>>>> @shady : yes i guess this is what question says:-
>>>> so acc to this below algo work , i didnt execute it but i guess it will
>>>> work
>>>>
>>>> void nextSmaller(int arr[],int n)
>>>> {
>>>> s1 s;
>>>> int i,next,ele;
>>>>
>>>> s.top=-1;
>>>> push(&s,0);
>>>>
>>>> for(i=1;i<n;i++)
>>>> {
>>>> next=arr[i];
>>>> if(isEmpty(&s))
>>>> {
>>>> ele=pop(&s);
>>>> while(arr[ele] > next)
>>>> {
>>>> swap(arr,ele,i);
>>>> next=arr[ele];
>>>> if(isEmpty(&s)==0)
>>>> {
>>>> break;
>>>> }
>>>> ele=pop(&s);
>>>> }
>>>> if(ele > next)
>>>> {
>>>> push(&s,ele);
>>>> }
>>>>
>>>> }
>>>>
>>>> push(&s,i);
>>>> }
>>>>
>>>> }
>>>>
>>>>
>>>> On Sun, Mar 25, 2012 at 4:36 PM, shady <[email protected]> wrote:
>>>>
>>>>> @gene
>>>>> i think for 3 4 2 you need to start from left most element, and then
>>>>> make substitutions one by one.
>>>>> so it will be
>>>>> 3 4 2
>>>>> 2 4 3
>>>>> 2 3 4
>>>>>
>>>>>
>>>>> @all i googled a bit, and found that O(n) solution is possible for it,
>>>>> any idea ?
>>>>>
>>>>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan <
>>>>> [email protected]> wrote:
>>>>>
>>>>>> +1 @saurabh...:P
>>>>>>
>>>>>> --
>>>>>> 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.
>>>>>
>>>>
>>>> --
>>>> 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.
>>>
>> --
>> 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.
>
--
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.
