Domain 1EasyCORE

Min Stack

The problem requires designing a stack that supports standard stack operations (`push`, `pop`, `top`) along with an additional operation `getMin` which retrieves the minimum element in constant time. The stack should handle integer values within the range of `-2^31` to `2^31 - 1`. The methods `pop`, `top`, and `getMin` will always be called on non-empty stacks, and there can be up to `3 * 10^4` calls made to these operations.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Stack#Design

155. Min Stack

Model: qwen2.5-coder:14b
Topics: Stack,Design
FAANG asked: 1
Acceptance rate: 46.8%


Problem Breakdown

The problem requires designing a stack that supports standard stack operations (push, pop, top) along with an additional operation getMin which retrieves the minimum element in constant time. The stack should handle integer values within the range of -2^31 to 2^31 - 1. The methods pop, top, and getMin will always be called on non-empty stacks, and there can be up to 3 * 10^4 calls made to these operations.

Inputs:

  • push(val): An integer value to be pushed onto the stack.
  • pop(): No input; removes the top element of the stack.
  • top(): No input; returns the top element of the stack without removing it.
  • getMin(): No input; retrieves and returns the minimum element in the stack.

Outputs:

  • push(val), pop(): No output (void).
  • top(): Returns the integer value at the top of the stack.
  • getMin(): Returns the integer value which is the minimum element in the stack.

Implicit Constraints/Edge Cases:

  • The stack should support constant time operations for all methods.
  • Handling negative numbers and potential overflow scenarios within the given range.
  • Ensuring that the stack remains consistent after each operation.

Intuition

A brute-force approach would involve maintaining a standard stack and iterating through it to find the minimum element whenever getMin is called. This approach would result in O(n) time complexity for the getMin operation, which is not efficient enough given the constraints.

The key insight is to maintain an auxiliary data structure that keeps track of the minimum values at each level of the stack. By doing so, we can retrieve the minimum element in constant time. A common approach is to use a second stack where each element represents the current minimum value up to that point in the main stack.

Approach

  1. Data Structures:

    • Use two stacks: stack for storing all elements and min_stack for keeping track of the minimum values.
  2. Operations:

    • Push(val):
      • Push the value onto the stack.
      • If min_stack is empty or the current value is less than or equal to the top of min_stack, push the value onto min_stack.
    • Pop():
      • Pop the value from the stack.
      • If the popped value is equal to the top of min_stack, pop it from min_stack as well.
    • Top():
      • Return the top element of the stack.
    • GetMin():
      • Return the top element of the min_stack.

This approach ensures that all operations are performed in constant time, O(1).

Complexity Analysis

  • Time Complexity:

    • All operations (push, pop, top, getMin) have a time complexity of O(1).
  • Space Complexity:

    • The space complexity is O(n) where n is the number of elements pushed onto the stack. This is because we use an additional stack to keep track of minimum values.

Solution

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.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.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

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

Edge Cases Handled

  • Empty Stack: The problem constraints ensure that pop, top, and getMin are never called on an empty stack, so we don’t need to handle this case.
  • Negative Numbers: The solution correctly handles negative numbers as it compares values directly without any assumptions about their positivity or negativity.
  • Overflow/Underflow: Given the constraints of integer ranges, Python’s list operations inherently handle overflow and underflow scenarios.