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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Min Stack

Number: 155

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, Google, Microsoft, Meta, Yandex, Apple, Salesforce, Oracle, LinkedIn, Tinkoff, Informatica, Lyft, Adobe, Yahoo, Walmart Labs, ServiceNow, Qualcomm, Agoda, IMC, Veeva Systems, Uber, Snap, Zenefits

Problem Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. The stack should implement the following functions:

  • push(val): adds the element val to the stack.
  • pop(): removes the element on the top of the stack.
  • top(): retrieves the top element of the stack.
  • getMin(): retrieves the minimum element currently in the stack.

Key Insights

  • Use an auxiliary data structure to track the current minimum element.
  • A common approach is to use two stacks: one regular stack for all elements and a second stack to keep track of the minimum values.
  • When pushing a new element, push it onto the main stack and also update the min stack if the element is less than or equal to the current minimum.
  • When popping, if the popped element is equal to the top of the min stack, pop from the min stack as well.
  • This design guarantees that all operations (push, pop, top, getMin) run in constant time, O(1).

Space and Time Complexity

Time Complexity: O(1) per operation (push, pop, top, getMin) Space Complexity: O(n), where n is the number of elements in the stack, since an additional stack is used to keep track of minima.

Solution

The solution involves using two stacks:

  1. Main Stack: Stores all the elements.
  2. Min Stack: Stores the minimum elements encountered so far.

When an element is pushed, we compare it with the top of the min stack. If it is smaller than or equal to the current minimum, we also push it onto the min stack. For the pop operation, if the element being popped is the same as the top of the min stack, we pop from the min stack as well. This approach ensures that the getMin operation always returns the top element of the min stack, which is the current minimum in constant time.

Code Solutions

# Python implementation of MinStack with detailed comments

class MinStack:
    def __init__(self):
        # Main stack to store all values
        self.stack = []
        # Auxiliary stack to store minimum values
        self.min_stack = []

    def push(self, val: int) -> None:
        # Push value onto main stack
        self.stack.append(val)
        # If min_stack is empty or the new value is less than or equal to current minimum, push it onto min_stack
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

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

    def top(self) -> int:
        # Return the top value from main stack without removing it
        return self.stack[-1]

    def getMin(self) -> int:
        # Return the minimum value from min_stack
        return self.min_stack[-1]
        
# Example usage:
# minStack = MinStack()
# minStack.push(-2)
# minStack.push(0)
# minStack.push(-3)
# print(minStack.getMin()) # -> -3
# minStack.pop()
# print(minStack.top())    # -> 0
# print(minStack.getMin()) # -> -2
← Back to All Questions