155. Min Stack

Prompt

We want to design a stack class called MinStack that supports the following 4 operations/ methods:

  1. push(): pushes or adds an element (val) onto the stack
  2. pop(): removes the element on the top of the stack
  3. top(): retrieves the top element of the stack
  4. getMin(): retrieves the minimum element in the stack

Approach

The key to this problem is to keep track of the latest minimum value whenever we append or push an element into the stack or array. In other words, we would have a corresponding value to the value we are pushing that represents the minimum value at that point in time. We can accomplish this by either storing each element in the stack as a tuple or by maintaining 2 separate stacks, 1 stack for dealing with the elements that are being added and the other stack for storing the corresponding minimum value at that point.

Code

In the code below, by keeping track of the latest minimum element (minVal), as we add each value (val) into stack, we also make sure to add or append minVal to the other stack (minStack), which creates that corresponding relationship. Therefore, whenever we call the pop() method, we remove the top most element from both of the stacks which is exactly what we want because if we make a subsequent call to the getMin() method after calling pop(), we’ll retrieve the latest, valid minimum value.

Code in Python

--

--

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
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com