We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Min Stack

Difficulty: Medium

Problem Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Key Insights

  • The stack must support four main operations: push, pop, top, and getMin.
  • Each operation must be performed in O(1) time complexity.
  • To efficiently track the minimum element, we can use an auxiliary stack.

Space and Time Complexity

Time Complexity: O(1) for all operations (push, pop, top, getMin)
Space Complexity: O(n) where n is the number of elements in the stack (due to the auxiliary stack for tracking minimums).

Solution

We will implement a MinStack class that uses two stacks: one for storing the actual stack elements and another for storing the minimum elements. The minimum stack will only store elements when they are less than or equal to the current minimum. This allows us to retrieve the minimum element in constant time by simply looking at the top of the minimum stack.

  1. Data Structures: Use two stacks:

    • stack: to store the actual elements.
    • minStack: to store the minimum elements.

  2. Algorithm:

    • push(val): Push the value onto the stack. If minStack is empty or val is less than or equal to the top of minStack, push val onto minStack.
    • pop(): Pop the top value from stack. If the popped value is equal to the top of minStack, pop from minStack as well.
    • top(): Return the top value from stack.
    • getMin(): Return the top value from minStack, which is the minimum element.

Code Solutions

class MinStack:
    def __init__(self):
        self.stack = []    # Main stack to store elements
        self.minStack = [] # Auxiliary stack to store minimums

    def push(self, val: int) -> None:
        self.stack.append(val)  # Push value onto main stack
        # Push onto minStack if it's empty or val is <= current minimum
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)

    def pop(self) -> None:
        if self.stack:
            popped_value = self.stack.pop()  # Pop from main stack
            # If popped value is the current minimum, pop from minStack as well
            if popped_value == self.minStack[-1]:
                self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None  # Return top value of main stack

    def getMin(self) -> int:
        return self.minStack[-1] if self.minStack else None  # Return top value of minStack
← Back to All Questions