Problem link - Min Stack in
Problem statement
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:
The key idea is to use two stacks to maintain the main stack and track the minimum element efficiently. We use one stack (s) for storing all elements and another stack (minStack) for tracking the minimum values.
- Initialization: Start by initializing the minStack with a very large value to handle the minimum comparisons properly.
- Push Operation: When pushing a new value onto the stack, add it to the main stack. Also, update the minStack by pushing the new value if it is smaller than or equal to the current minimum.
- Pop Operation: Remove the top element from both the main stack and the minStack if the top element of the main stack is equal to the top of the minStack . This ensures that the minStack always contains the minimum values.
- Top Operation: Return the top element of the main stack.
- GetMin Operation: Retrieve the top element of the minStack , which represents the minimum value in the main stack.
Time Complexity:
- O(1) for each operation (push, pop, top, getMin), as all operations are performed in constant time using the stacks.
Space Complexity:
- O(n) where n is the number of elements in the stack. The space complexity accounts for storing the elements in the data structure.