I am getting "TLE" in basic stack problem

I am getting “TLE” after getting correct o/p till 15 test cases, what is the mistake ?

problem link – Maximum Element | HackerRank

``````#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main()
{
stack<int> s;
stack<int> dup;

int n;
cin >> n;
while(n--)
{
int t,x;
cin >> t;

if(t==1)
{
cin >> x;
s.push(x);
}
else if(t==2)
{
s.pop();
}
else
{
int maxi = 0;
while(!s.empty())
{
dup.push(s.top());
maxi = max(maxi,s.top());
s.pop();
}

while(!dup.empty())
{
s.push(dup.top());
dup.pop();
}

cout << maxi << '\n';

}

}
return 0;
}
``````

Your code’s time complexity is O(N) for Query 3 (Finding maximum element in the stack), while the rest are implemented in O(1).
Here’s the solution.
Implement another stack, called MAX STACK.
It works like this.

• Let `st` be the actual stack you are supposed to implement.
• Let `mst` be the MAX Stack.
• Both of them have same height (same number of elements) at any instance.
• When ever you push an element `x` to `st`, you will also push `max(mst.top(), x)` to MAX Stack.
• When ever you are supposed to pop (Query 2), pop from both stacks.
• For query of type 3 (Print maximum element), just return `mst.top()`.
1 Like

Here’s the code.

``````#include <bits/stdc++.h>
using namespace std;
static inline int max(int a, int b) {
return a>b?a:b;
}
int main() {
stack <int> st;
stack <int> mst;
int q;
cin >> q;
while(q--) {
int query;
cin >> query;
if(query == 1) {
int x;
cin >> x;
if(st.empty()) {
st.push(x);
mst.push(x);
}
else {
mst.push(max(mst.top(), x));
st.push(x);
}
}
else if(query == 2) {
st.pop();
mst.pop();
}
else {
cout << mst.top() << endl;
}
}
return 0;
}

``````
1 Like