LeetCode 155. MinStack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

MinStack minStack = new MinStack();
minStack.getMin(); // return -3
minStack.top(); // return 0
minStack.getMin(); // return -2


  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.


Stack by default supports push(), pop(), top() in O(1) time complexity. But getting the minimum value in O(1) is not default operation of stack data structure.

Lets take the example [“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]

Here after 3 push() operations, how can we get the minimum value from the stack? Naïve way would be look at every single element of the stack to get the minimum which is O(N) operation.

[-2] whats the minimum at this point? -2

[-2,0] ==> min value : 0

[-2,0,-3] ==> min value = -3

How about keeping a single variable to keep track of the minimum value? No it wont work why?

Because for example if you pop() from [-2,0,-3] , that would be [-2,0] and correct answer of new getMin() should be at this point: -2. How can we keep the min value at every element?

So what we need is two stacks : (1) Stack for keeping track of elements pushed into the stack (2) MinStack to store “minimum so far” for each element added to the stack.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store


Passionate about problem solving; #WritesOnQuora #VoraciousReader #MBTIEnthusiast #LovePsychology https://www.quora.com/profile/Shaila-Hegde-2