Stack with a minimum

Question

A practice interview question:

How would you design a stack which, in addition to push and pop, also has a function getMin which returns the minimum element? Push, pop and min should all operate in O(1) time.

class stackWithMin
{
private:
 std::vector<int> stack;
 std::vector<int> minLoc;
 int min, current, minCurrent;
public:
 stackWithMin()
 {
 min = NULL;
 current = 0;
 minCurrent = 0;
 }
 void print()
 {
 std::cout<<"Min: "<<min<<" --- ";
 for (int i=0;i<stack.size();i++)
 {
 std::cout<<""<<stack.at(i)<<", ";
 }
 std::cout<<""<<std::endl;
 }
 void push(int num)
 {
 stack.push_back(num);
 if(num<=min || current == 0)
 {
 minLoc.push_back(current);
 minCurrent++;
 min = num;
 }
 current++;
 print();
 }
 void pop()
 {
 if(current==0)
 {
 std::cout<<"Stack is empty"<<std::endl;
 return;
 }
 // Check if the number to be popped is the current lowests
 if(minLoc.at(minCurrent-1)==current-1)
 {
 if(minCurrent>1)
 {
 int loc = minLoc.at(--minCurrent-1);
 minLoc.pop_back();
 min = stack.at(loc);
 }
 // No more elements
 else
 {
 min = NULL;
 }
 }
 current--;
 stack.pop_back();
 print();
 return;
 }
 int getMin(){return min;}
};

• Jamal: Were you told to include print statements in all of the functions? Ideally, only print() should print something.
• nwp: After thinking about it for a while I was convinced it is not possible. Guess I would have failed to get the job.

Answer 1

Here are some things that may help you improve your code:

Simplify the algorithm

Although it would take more space to store, a simpler algorithm would be to simply use minLoc as the current minimum. If you did so, then getMin() would simply be return minLoc.back();

Eliminate redundant variables

Even if you don't care for that particular algorithm, you can remove the variables min, current and minCurrent and also simplify the code:

void push(int num)
{
 stack.push_back(num);
 if (minLoc.size() == 0 || num < stack[minLoc.back()]) 
 minLoc.push_back(stack.size()-1);
 print();
}
void pop()
{
 // Check if the number to be popped is the current lowest
 if(minLoc.size() && minLoc.back() == stack.size()-1)
 minLoc.pop_back();
 stack.pop_back();
 print();
}
int getMin() const {
 return minLoc.size() ? stack[minLoc.back()] : 0;
}

Use const where possible

The getMin function doesn't (and shouldn't) modify the underlying stack, so it should be declared const. The same is true for the print function.

Avoid using index variables

Rather than using an index variable i in the print routine and then calling at() for each iteration, use iterators instead. For example, you could use this:

std::copy(stack.cbegin(), stack.cend(), 
 std::ostream_iterator<int>(std::cout, ", "));

Omit empty strings

The current code for print includes this line:

std::cout<<""<<stack.at(i)<<", ";

There's no need for the empty string in that line.

Use whitespace to improve readability

To take the previously quoted line as an example, rewriting it with more whitespace makes it easier to read:

std::cout << stack.at(i) << ", ";

Don't use std::endl when '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Take care with signed versus unsigned

The code includes this line in the print function:

for (int i=0;i<stack.size();i++)

However, stack.size() is unsigned and i is signed. For consistency, it would be better to declare i as std::size_t which is the type returned by size().

Consider the user of the code

The std::vector::pop_back() returns void but provides a member function back() to allow a user of the code to access the last member before removing it from the vector. You might consider either returning the popped value in your implementation of pop or implementing a back function such as the one std::vector supplies.

• nwp: Why is 0 the minimum of an empty stack? Also there is a pretty good reason why pop_back does not return the object it popped.
• Edward: @nwp: 0 is an arbitrary choice that appears to have been the intent of the original code. As for the other issue, in this code, there is no way to access any members of the stack except via print. I consider that a design flaw for a practical design.

Answer 2

You wrote min = NULL; in two places. Any compiler would complain about that, if you compile with warnings enabled. (You do compile with warnings enabled, I hope?)

Your three instance variables min, current, and minCurrent seem to be redundant. current and minCurrent appear to be just current.size() and minLoc.size(), respectively. min is just current[minLoc.back()].

Answer 3

I think there is no answer since after each pop, if a current minimal value was popped, you need to determine the new minimal value in the stack. Only way to do that in O(1) is to have a sorted list of indices ready at that moment so you need to keep a sorted list, and there is no way to keep a list sorted in O(1) time since after each push you need at least O(2 log n) (binary search for instance) compares to look for the right spot to insert your new index in your sorted list.

An easy way to picture this is when you have for instance the following push's and pop's: push(2),push(4),push(3),push(5),...push(100),push(1),pop(), getMin()? Now your current minimal value (1) is popped and you need to have 2 ready for your next getMin() call but how do you know that 2 is minimal after you pop 1?

Answer 4

First things first:

• If you are trying an implementation of such sort, avoid STL containers. If so, you could well use stack. Just kidding. No.
• Think simple and be pertinent. A stack allows pop, push, peek. You cannot access any index in a stack (Ref: .at).

The implementation does it the wrong way with above facts ignored. Try with the following steps:

• A Node class with the following variables:

  1. Data (int data)
  2. Minimum (int min).
  3. Down pointer( Node* downPtr).

• A stackwithMin class with the following variable:

  1. Pointer to the top of the stack(Node* top);

• A StackwithMin class with the following methods:

  void push(int num)
  {
   // Calculate min = (empty stack)?num:Min(top->min,num);
   // Create a new node object 'node'.
   // node->data = num; node->min = min; node->downPtr = top;
   // Update the top i.e. top = node.
  }
  void pop(){
   // Node* prevTop = top;
   // update top = top->downPtr;
   // free prevTop.
  }
  int getMin()
  {
   // return top->min.
  }
  

All this will serve you in O(1). Its best you code it and represent the code again.