Designing a stack such that getMin() is both constant time and constant space I'm attempting the SpecialStack problem on GeeksforGeeks.


  Design a data-structure SpecialStack (using the STL of stack) that
  supports all the stack operations like push(), pop(), isEmpty(),
  isFull() and an additional operation getMin() which should return
  minimum element from the SpecialStack. Your task is to complete all
  the functions, using stack data-Structure.
  
  Input Format: The first line of input contains an integer T denoting
  the no of test cases. Then T test cases follow. Each test case
  contains two lines. The first line of input contains an integer n
  denoting the number of integers in a sequence. In the second line are
  n space separated integers of the stack.
  
  Output Format: 
  
  For each testcase, in a new line, print the minimum
  integer from the stack. 
  
  Your Task: 
  
  Since this is a function problem, you don't need to take
  inputs. Just complete the provided functions.
  
  Constraints: 
  
  1 &lt;= T &lt;= 100 
  
  1 &lt;= N &lt;= 100
  
  Example: 
  
  Input: 
  
  1 
  
  5 18 19 29 15 16 
  
  Output: 15


This is my code, including the Driver Code which was provided beforehand by the interface (the Driver Code is not modifiable):

// { Driver Code Starts
#include&lt;iostream&gt;
#include&lt;stack&gt;
using namespace std;
void push(int a);
bool isFull(int n);
bool isEmpty();
int pop();
int getMin();
//This is the STL stack (http://quiz.geeksforgeeks.org/stack-container-adaptors-the-c-standard-template-library-stl/).
stack&lt;int&gt; s;
int main(){
    int t;
    cin&gt;&gt;t;
    while(t--){
        int n,a;
        cin&gt;&gt;n;
        while(!isEmpty()){
            pop();
        }
        while(!isFull(n)){
            cin&gt;&gt;a;
            push(a);
        }
        cout&lt;&lt;getMin()&lt;&lt;endl;
    }
}// } Driver Code Ends
/*Complete the function(s) below*/

int minEle = 0; // Holds minimum element so far, as elements are pushed into stack

void push(int a)
{
     if (s.empty()) // If stack is empty push a and update minEle to a
     {
         minEle = a;
         s.push(a);
         return;
     }

     if (a &lt; minEle) // If a is less than minEle push (a-minEle) and update minEle to a
     {
         s.push(a - minEle);
         minEle = a;
         return;
     }

     if (a &gt; minEle) // If a is greater than minEle then push a but don't update minEle
     {
         s.push(a); 
     }
}


bool isFull(int n)
{
     return (s.size() == n);
}

bool isEmpty()
{
     return s.empty();
}

int pop()
{
    int top = s.top();
    if (top &lt; 0) // If the top element of stack is negative, we reconstruct the previous minEle 
    {
        minEle = minEle - top;
        s.pop();
    }
    else // Otherwise, just pop the top element
    {
        s.pop();
    }
    return top;
}

int getMin()
{
    return minEle;  
}


I've tried to explain the logic in the comments. This code gives the correct solution for all the test cases (with positive integers) I tried so far. For instance:


For Input:
2
5
18 19 29 15 16
11
34 335 1814 86 82 7 332 82 221 95 40
Your Output is:
15
7



which is the correct solution!

However, when I try to submit the code, it says:


Your program took more time than expected.Time Limit Exceeded
Expected Time Limit &lt; 1.3672sec
Hint : Please optimize your code and submit again.



As far as I understand, my code is \$\mathcal{O}(1)\$ in both time and space complexity and it uses no extra stacks. I'm not quite sure how to optimize the code runtime further. Any ideas?
If the grader is complaining about "time limit exceeded," it must be because some loop is executing too many times. All of your functions are clearly O(1) — they have no loops. So which loop is executing too many times? It must be the only loop in the entire program:

    while(!isFull(n)){
        cin&gt;&gt;a;
        push(a);
    }


Is it possible that your isFull is returning an incorrect answer? It's very straightforward: it tests s.size() == n. Is it possible that push(a) is not updating s.size()?

Reflowed for brevity and clarity, your push looks like this:

void push(int a)
{
     if (s.empty()) {
         minEle = a;
         s.push(a);
     } else if (a &lt; minEle) {
         s.push(a - minEle);
         minEle = a;
     } else if (a &gt; minEle) {
         s.push(a); 
     }
}


Do you see the bug yet? The problem is that when a == minEle, you never push anything! So if you get the input 1 1, you'll cause the test driver to loop forever... and that is what causes the timeout.

Also consider that there is no limit on the values of the integers you're given (just on the number of test cases T and the number of integers per test case N). So you'll have to find a way to make your code work with input -1 as well.

Consider maintaining a second stack std::stack&lt;int&gt; minEle alongside your std::stack&lt;int&gt; s. Does that make the problem easier?



EDITED TO ADD: If you kept the current push, then you could rewrite it for even more clarity by factoring the s.push to the bottom of the function, like this:

void push(int a)
{
     if (s.empty()) {
         minEle = a;
     } else if (a &lt; minEle) {
         a -= std::exchange(minEle, a);
     } else if (a &gt; minEle) {
         // do nothing
     } else {
         return;  // uh-oh!
     }
     s.push(a);
}


This shows clearly that each call to push results in one and only one call to s.push (except for the buggy case).