{x}
blog image

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.

 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

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

 

Constraints:

  • -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.

Solution Explanation:

This problem requires designing a stack data structure that supports push, pop, top, and getMin operations all in O(1) time complexity. A single stack is insufficient because finding the minimum element efficiently would require traversing the stack (O(n) time). The solution utilizes two stacks:

  • stk1: This stack stores the actual elements pushed onto the min stack.
  • stk2: This stack stores the minimum element encountered so far at each point in time.

Algorithm:

  1. __init__/Constructor: Initializes both stacks. stk2 is initialized with a large value (infinity in Python, Integer.MAX_VALUE in Java, etc.) to ensure the first element pushed will become the minimum.

  2. push(val): When pushing a value val:

    • Push val onto stk1.
    • Push the minimum between val and the current minimum (top of stk2) onto stk2.

  3. pop(): When popping an element:

    • Pop the top element from both stk1 and stk2. This maintains the invariant that stk2 always reflects the minimum element seen so far after the pop operation.

  4. top(): Returns the top element of stk1.

  5. getMin(): Returns the top element of stk2, which is the current minimum element in the stack.

Time and Space Complexity:

  • Time Complexity: All operations (push, pop, top, getMin) have O(1) time complexity because they involve only stack operations (push and pop) which take constant time.
  • Space Complexity: The space complexity is O(N), where N is the maximum number of elements in the stack, because we use two stacks to store the data.

Example Walkthrough (using Python):

Let's trace the example ["MinStack","push","push","push","getMin","pop","top","getMin"] with [[],[-2],[0],[-3],[],[],[],[]]:

  1. MinStack(): stk1 = [], stk2 = [inf]
  2. push(-2): stk1 = [-2], stk2 = [inf, -2]
  3. push(0): stk1 = [-2, 0], stk2 = [inf, -2, -2]
  4. push(-3): stk1 = [-2, 0, -3], stk2 = [inf, -2, -2, -3]
  5. getMin(): Returns -3 (top of stk2)
  6. pop(): stk1 = [-2, 0], stk2 = [inf, -2, -2]
  7. top(): Returns 0 (top of stk1)
  8. getMin(): Returns -2 (top of stk2)

This approach ensures that all operations are performed in O(1) time, fulfilling the requirements of the problem. The provided code snippets in different languages demonstrate this implementation. Note the slight variations in handling infinity/maximum integer values across different languages.