my code is not working for Input:
10 3 *12* 4 2 9 13 0 8 11 1 7 5 6
Its Correct output is:
12 12 *13* 9 9 13 -1 8 11 -1 7 -1 6 -1
And Your Code's output is:
12 12 *-1* 9 13 13 -1 8 11 -1 7 -1 6 -1
what I can see, it is because in the while(!s.empty() && a>s.top()) part I m not storing the index values for those elements for which a<s.top(), I'm not able to think of any way to do so.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a,i,c[n];
memset(c,-1,sizeof(c));
stack <int> s;
for(i=0;i<n;i++){
cin>>a;
if(s.empty()){
s.push(a);
}
else{
if(a>s.top()){
int k=i;
while(!s.empty() && a>s.top()){
s.pop();
c[k-1]=a;
k--;
}
s.push(a);
}
else{
s.push(a);
continue;
}
}
}
for(i=0;i<n;i++)
cout<<c[i]<<" ";
cout<<endl;
}
}
There is a little bug in your code. When you update the value of c[index]=value, the index is not correct. While processing, you pop out some of the elements from the stack and push the value at the end(example: a value at a location of 10 can be pushed at anywhere between 0 and 10), but during stepping backward you don't know what was the correct location of that value.
So, I made slide changes in your code, kept track of the location of the value along with the value itself. So, when I update c[index]=value, I know the correct index of s.top() element.
int main() {
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a,i,c[n];
memset(c,-1,sizeof(c));
stack < pair<int,int> > s;
for(i=0;i<n;i++){
cin>>a;
if(s.empty()){
s.push({a,i});
}
else{
if(a>s.top().first){
while(!s.empty() && a>s.top().first){
c[s.top().second]=a;
s.pop();
}
s.push({a,i});
}
else{
s.push({a,i});
continue;
}
}
}
for(i=0;i<n;i++)
cout<<c[i]<<" ";
cout<<endl;
}
}
Input & Output:
1
15
14 10 3 12 4 2 9 13 0 8 11 1 7 5 6
-1 12 12 13 9 9 13 -1 8 11 -1 7 -1 6 -1