155. Min Stack
Today, we’ll be looking at the following problem:
155. Min Stack
Min Stack - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…
We want to design a stack class called MinStack that supports the following 4 operations/ methods:
- push(): pushes or adds an element (val) onto the stack
- pop(): removes the element on the top of the stack
- top(): retrieves the top element of the stack
- getMin(): retrieves the minimum element in the stack
We have the choice of implementing a stack data structure either using an array or a linked list. For this approach, we’ll be implementing the former.
The challenging component to this problem is to implement a solution with O(1) time complexity for each of the operations listed above. For each of the operations from 1 to 3 respectively, pushing an element at the end of an array is, on average, is O(1) time, and conversely removing an element at the end of an array is O(1) time. Indexing and retrieving the last element in an array also is O(1) time.
However, how about retrieving the minimum element in a stack? One would naturally think this, in the worst case, would take linear time because we would have to iterate through the entire array and find the minimum value among all the elements.
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.
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.
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at email@example.com