DEV Community

Yash
Yash

Posted on

Design a stack that supports getMin() in O(1) time and O(1) extra space

I came across this interview question the other day, and when I saw the solution, I learned something new. I decided to share it for anyone interested. The task is to design a variation of the stack data structure but with the additional functionality of fetching the current minimum element in the stack without using more than constant extra space. Try to work it out on your own; I will lay out one of the solutions that I found. If your solution is something else, I would love to know it. Anyway, here it is:

The Idea

Whenever there is a new minimum pushed to the stack, use the old minimum in a way to relate to the new minimum while simultaneously being able to regenerate the old minimum. Here is a clearer representation:

Maintain one extra variable associated with the stack, let it be minEle.

Push(int x):

  • Case 1: If the stack is empty, insert x and set minEle = x.
  • Case 2: If x >= minEle, simply push x.
  • Case 3: If x < minEle (when x is the new minimum), push 2*x - minEle. This is because 2*x - previous_minEle < x is always true. Then, set minEle = x.

Pop():

  • Case 1: If stk.top() >= minEle, just pop the topmost element.
  • Case 2: If stk.top() < minEle, then we know that this is actually 2*minEle - previous_minEle. Since we know minEle, we can find the previous minEle, update minEle, and then pop the top element.

I have written an implementation in C++ using an object-oriented approach here: MinStack.cpp.

Here is a sample test run:

Image description

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up