this is O(n) solution and using O(n) space.......
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
void leader_count(vector<int> v,int *ar)
{
stack<int> s;
int n=v.size();
int i=n-1;
while(i>=0)
{
if(s.empty())
{
ar[--n]=0;
s.push(i);
i--;
}
else
{
if(v[i] >= v[s.top()])
{
ar[--n]=s.top();
s.push(i);
i--;
}
else
{
s.pop();
}
}
}
for(int i=v.size()-1;i>=0;i--)
if(ar[i]!=0)
ar[i]=ar[ar[i]]+1;
}
main()
{
int i;
vector<int> v;
while(cin>>i)
v.push_back(i);
int *ar=new int[v.size()];
leader_count(v,ar);
for(int i=0;i<v.size();i++)
cout<<ar[i]<<" ";
}
--
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.
