a crude algo,
for(i=end to start)
{
while(!stk.empty())
{
if(arr[i]<arr[stk.top])
pop();
else
break;
}
if(!stk.empty())
l = arr.length-1;
else
l = stk.top;
output[i]=l-i-1;
stk.puch(i);
}
This will be O(n). Correct me I am wrong anywhere..
On Tue, Jul 26, 2011 at 5:49 PM, Akshata Sharma
<[email protected]>wrote:
> @Piyush, using stack i guess it can be done in O(n)
>
>
> On Tue, Jul 26, 2011 at 5:42 PM, Shikhar <[email protected]> wrote:
>
>> @ankit: you are right...sorry about the error
>>
>> On Jul 26, 5:11 pm, ankit sambyal <[email protected]> wrote:
>> > The O/P of ur example should be 2,2,1,1,1,-1,-1
>> > or am I getting it wrong ??
>>
>> --
>> 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.
