I am getting "TLE" in basic stack problem

general
, ,
1

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;
}
2

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
3

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