Min Stack Design with O(1) Time Complexity

LeetCode Problem 155 "Min Stack": 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. Approach: we can implement a single stack and store values as tuples (current element, min so far). But wait ... consider edge case when we pop and the stack becomes empty, so to handle this we consider two conditions- one when stack becomes empty, we set min so far to +ve infinity again, second whenever we pop elements, if stack is not empty, we update min so far to the top of the stack's min so far. In this way we can keep track of the minimum element upto a specific stack level. Time complexity of all the operations: O(1) #Python #LeetCode #ProblemSolving #DSA #InterviewPrep #DataStructures #Algorithms #Programming

  • text

To view or add a comment, sign in

Explore content categories