Coding interview Essentials

22. Min stack

Min stack

Introduction

This chapter introduces a very popular question among companies like Yahoo, Amazon, Adobe and Microsoft. The question is simple and concerns designing a data structure for performing stack operations that is also able to keep track of the minimum element that is currently present in the stack. There is a simple, short and elegant solution for this problem, however, it is important understand the approach thoroughly as it is likely you may be asked a similar problem during the on-line screening steps of the interview process or during the first on-site.

Problem statement

Design a stack that supports:

  • push(x): the element \(x\) is pushed onto the stack

  • pop(): removes the top of the stack

  • top(): retrieve the top of the stack

  • get_min(): retrieve the minimum among all elements present in the stack.


Suppose the following set of operation on the stack are performed on a newly constructed and empty stack \(S\):

  • push(1): \(S=[1]\)

  • push(5): \(S=[5,1]\)

  • push(3): \(S=[3,5,1]\)

  • top(): \(S=[3,5,1]\), returns \(3\)

  • pop(): \(S=[5,1]\)

  • get_min(): \(S=[5,1]\), return \(1\)

  • push(0): \(S=[0,5,1]\)

  • get_min(): \(S=[0,5,1]\), returns \(0\)


Suppose the following set of operations on the stack are performed on a newly constructed and empty stack \(S\):

  • push(3): \(S=[3]\)

  • push(5): \(S=[5,3]\)

  • push(1): \(S=[1,5,3]\)

  • get_min: \(S=[1,5,3]\), return \(1\)

  • pop(): \(S=[5,3]\), returns \(3\)

  • get_min(): \(S=[5,3]\), return \(3\)

  • pop(): \(S=[1]\), return \(1\)

  • pop(): \(S=[]\)

  • pop(): raise std::logic_error

Clarification Questions

What should be done when get_min() or top() or pop() are performed on an empty stack?

You should throw a std::logic_error exception with a sensible and short description.

Discussion

This problem can become quite tricky if approached from the wrong angle. We will discuss two solutions both of which are good options to use during an actual interview.

Linear Space solutions

Stack of pairs

This first solution uses an additional space (\(2\times\)) to store for each element of the stack the information about the minimum among the elements still present in the stack. In order to do so we use a stack of pairs, where the first item of each pair is the actual element we want to push into our data structure and the second is the minimum value among the elements we have seen so far. Given this set-up the operations can then be implemented as follows:

  • push(x). We will store on top of the stack of pair either the pair \(\{x,x\}\) if the stack is empty or {std::min(x,get_min()).

  • top(x) returns the first element of the top of the stack of pair if the stack is not empty, otherwise it throws an exception.

  • pop(x) will call pop on the stack of pairs if the stack is not empty, otherwise raises an exception.

  • get_min(x) returns the second element of the top of the stack of pair if the stack is not empty, otherwise it throws an exception.

Listing [list:min_stack:stackpairs] shows a possible implementation of this idea.

Listing 1: Solution to the problem of designing a min stack using a stack of pairs.

template <class T>
class min_stack_stack_pair
{
 public:
  void push(const T& x)
  {
    const auto nm = q.size() > 0 ? std::min(x, getMin()) : x;
    q.push({x, nm});
  }

  void pop()
  {
    guard_empty_stack();
    q.pop();
  }

  T top()
  {
    guard_empty_stack();
    return q.top().first;
  }

  T getMin()
  {
    guard_empty_stack();
    return q.top().second;
  }

 protected:
  void guard_empty_stack()
  {
    if (q.size() <= 0)
      throw std::logic_error("Invalid operation on an empty stack");
  }

 private:
  std::stack<std::pair<T, T>> q;
};

Two stacks

The solution presented in Section 26.3.1.1 can be improved upon (even though will remain asymptotically the same in the worst case) by realizing that there is no need to have a copy of the minimum element for each element of the stack. What we really need is to have a second stack that contains the sequence of minimum elements as they are inserted.

We can achieve that by using an additional stack to store the minimums. Every time we try to push an element that is lower than the top of this stack, we will push it into Given this additional stack we can implement all the operations as follows:

  • push(x). We will store \(x\) on top of the stack (where we store the actual elements are they are given to us) and only if x <= get_min() we will also push \(x\) to the stack of minimums. This way we keep the information about the current minimum without losing the information about the previous ones which will be useful whenever in the future it will be removed from the stack (if \(x\) is the new minimum).

  • top(x) returns the first element of the top of the stack if it is not empty, otherwise it throws an exception.

  • pop(x) if the stack is not empty, it will call pop on the stack, and if the element we are popping is equal to the top of the stack of minimums we will also pop from that stack. We need to react to the fact that the current minimum is changing.

  • get_min(x) returns the top of the stack (the stack of minimums) if the stack is not empty, otherwise it throws an exception.

This solution has the advantage of not using as much space as the one presented in Section 26.3.1.1 when e.g. a sequence of increasing number is pushed. In that case the minimum will be the first element, and it will never change. Also note that because of the way the stack of minimums is used, it will always contains a decreasing sequence of values (after all we only push to it if the new element is smaller than the top).

This idea can be implemented as shown in Listing [list:min_stack:doublestack]

Listing 2: Solution to the problem of designing a min stack using a two stacks.

template <class T>
class min_stack_two_stacks
{
 public:
  void push(const T& x)
  {
    if (x <= getMin() || minimums.size() == 0)
      minimums.push(x);
    elements.push(x);
  }

  void pop()
  {
    guard_empty_stack();
    if (getMin() == elements.top())
      minimums.pop();
    elements.pop();
  }

  T top()
  {
    guard_empty_stack();
    return elements.top();
  }

  T getMin()
  {
    guard_empty_stack();
    return minimums.top();
  }

 protected:
  void guard_empty_stack()
  {
    if (elements.size() <= 0)
      throw std::logic_error("Invalid operation on an empty stack");
  }

 private:
  std::stack<int> elements;
  std::stack<int> minimums;
};

Constant space

Despite the fact that the solution presented in Section 26.3.1.2 is likely already sufficient for a coding interview, it is worth considering an additional solution that works only for integral types and that works in constant space. This is a big improvement relative to the other solutions above, however, the downside is that it only works for a very limited number of types.

If, as already discussed, the key challenge of this problem is how to retrieve the current minimum for each element in the stack and store such information without using additional then the answer may be that we need to encode such information into the elements themselves.

The idea is simple: we will store the elements in a std::stack, \(S\), and we will also keep track of the current minimum element in a variable, min_el. The operations on the data structure can be implemented as follows:

  • push(x) we have two cases here:

    1. if the stack is empty: push \(x\) to \(S\) and set

    2. otherwise:

      • if just push x to \(S\) leaving untouched.

      • if , push to \(S\) and set .

  • pop() two cases here as well depending on the element to be removed \(y\) (at the top of the stack):

    1. if , \(y\) is removed from the stack leaving untouched

    2. otherwise: if , set

    The key idea here is that we can retrieve the previous minimum element given the current one and the value that is currently on the stack.

  • top() very similar to the operation, without the update on the variable

  • get_min(x), returns

When an element \(x\) is less than the current minimum i.e. , the value will be inserted in the stack and the minimum set to \(x\). The fact that (remember that ) is important given that when this element will be popped out from the stack we will be able to tell that the minimum is changing because we will see that and therefore we will update the minimum element accordingly.

The idea above is shown in Listing [list:min_stack:constspace]. Note how the template class will only compile for integral types thanks to [@cit::std::enableif].

Listing 3: Solution to the problem of designing a min stack of integer working in constant space and linear time.

template <class T,
          typename = typename std::enable_if<std::is_integral<T>::value>::type>
class min_stack_int_constant_time
{
 public:
  void push(const T& x)
  {
    T new_min_el = min_el;
    if (elements.size() == 0)
    {
      elements.push(x);
      new_min_el = x;
    }

    if (x < elements.top())
    {
      elements.push(2 * x - min_el);
      new_min_el = x;
    }
    else
    {
      elements.push(x);
    }
    min_el = new_min_el;
  }

  void pop()
  {
    guard_empty_stack();
    const T top_el = elements.top();
    elements.pop();

    if (top_el < min_el)
    {
      min_el = 2 * min_el - top_el;
    }
  }

  T top()
  {
    guard_empty_stack();
    const T top_el = elements.top();
    if (top_el >= min_el)
      return top_el;
    else
      return min_el;
  }

  T getMin()
  {
    guard_empty_stack();
    return min_el;
  }

 protected:
  void guard_empty_stack()
  {
    if (elements.size() <= 0)
      throw std::logic_error("Invalid operation on an empty stack");
  }

 private:
  std::stack<T> elements;
  T min_el;
};

Common Variations

Design and implement a max stack data structure supporting the following operations:

  • push(x): the element \(x\) is pushed onto the stack

  • pop(): removes the top of the stack

  • top(): retrieve the top of the stack

  • get_max(): retrieve the maximum among all elements present in the stack.