Published on

Design a Min Stack

Authors
  • Name
    Twitter

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.

  • Constraints

    • -2**31 <= val <= 2**31 - 1
    • Methods pop, top and getMin operations will always be called on non-empty stacks.
    • At most 3 * 10**4 calls will be made to push, pop, top, and getMin.
  • Examples:

    • 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
    

Solutions

Approach 1 : using two stacks

You can design a stack that supports push, pop, top, and retrieving the minimum element in constant time using two stacks: one for the actual elements (let's call it the "main stack") and another for keeping track of the minimum elements (let's call it the "min stack")


class MinStack(object):
    def __init__(self):
        self.main_stack = []  # The main stack to store elements
        self.min_stack = []   # The min stack to keep track of minimum elements

    def push(self, val: int) -> None:
        self.main_stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.main_stack:
            if self.main_stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.main_stack.pop()

    def top(self) -> int:
        if self.main_stack:
            return self.main_stack[-1]
        else:
            return None

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]
        else:
            return None

# Example usage:
# min_stack = MinStack()
# min_stack.push(3)
# min_stack.push(5)
# min_stack.push(2)
# min_stack.push(1)

# print("Top element:", min_stack.top())    # Output: 1
# print("Minimum element:", min_stack.getMin())  # Output: 1

# min_stack.pop()
# print("After popping, top element:", min_stack.top())    # Output: 2
# print("After popping, minimum element:", min_stack.getMin())  # Output: 2

Explanation

The design of this stack, which supports push, pop, top, and retrieving the minimum element in constant time, works because it uses an auxiliary stack (min_stack) to keep track of the minimum element at any given time without the need for additional iterations or searching through the main stack. Let's break down why this approach works:

  1. Main Stack (main_stack) for Storing Elements:

    • The main_stack is used to store all the elements that are pushed onto the stack. It behaves like a regular stack for maintaining the order of elements.
  2. Auxiliary Stack (min_stack) for Tracking Minimums:

    • The min_stack is used to keep track of the minimum element at any point in time.
    • When an element is pushed onto the main_stack, it's compared with the top element of the min_stack.
    • If the element is less than or equal to the top element of the min_stack, it's pushed onto the min_stack. This ensures that the min_stack always contains the minimum element seen so far.
  3. Efficient Retrieval of Minimum Element:

    • Since we are keeping track of the minimum element in the min_stack, retrieving the minimum element is a constant-time operation. We simply look at the top element of the min_stack.
  4. Consistent Popping of Elements:

    • When an element is popped from the main_stack, we also check if it's the same as the top element of the min_stack. If they match, we pop the top element from the min_stack as well. This ensures that the min_stack always correctly reflects the minimum element.

Here's why this approach works efficiently:

  • Pushing an element onto the stack (both main_stack and min_stack) is a constant-time operation, O(1).
  • Popping an element from the stack (both main_stack and min_stack) is also a constant-time operation, O(1).
  • Retrieving the top element of the main_stack and min_stack is a constant-time operation, O(1).

By maintaining the min_stack to track minimum elements as elements are pushed and popped from the main_stack, this design allows you to efficiently keep track of the minimum element and perform all stack operations (push, pop, top) in constant time, meeting the requirements of the problem.

References