Designing a stack such that getMin() is both constant time and constant space

Question

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 <= T <= 100

1 <= N <= 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<iostream>
#include<stack>
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<int> s;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,a;
        cin>>n;
        while(!isEmpty()){
            pop();
        }
        while(!isFull(n)){
            cin>>a;
            push(a);
        }
        cout<<getMin()<<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 < minEle) // If a is less than minEle push (a-minEle) and update minEle to a
     {
         s.push(a - minEle);
         minEle = a;
         return;
     }

     if (a > 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 < 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 < 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?

Answer 1

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>>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 < minEle) {
         s.push(a - minEle);
         minEle = a;
     } else if (a > 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<int> minEle alongside your std::stack<int> 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 < minEle) {
         a -= std::exchange(minEle, a);
     } else if (a > 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).

Answer 2

Avoid Global Variables

In the code there are 2 global variables:

int minEle = 0;
stack<int> s;

Using global variables is something that all experienced programmers avoid. Global variables make the code very hard to write, debug and maintain. It is very difficult in programs larger than this one to local where a global variable is modified. Global variables can also cause C and C++ program that consist of multiple files not to link into an executable image. This is discussed on stackoverflow.com, however, if you do a Google Search on why are global variables bad you will find many more references.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Variable Types

It would be better to use the variable type size_t rather than int for the variables t and n. The restrictions on both t and n indicates that the value will never be less than 1, which means the value will never be less than zero. The variable type size_t is unsigned.

Variable Names

Single letter variable names such as t, n and s make reading and debugging code very difficult. The variable names should really indicate what the variable is for, examples testCount, elementCount, specialStack. The variable minEle, might be better named as minElement.