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?