BL
U

84. Min Stack Design with O(1) Minimum Retrieval

Easy

Problem Description

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1)O(1) time.

Support QQ operations:

  • •push x: Push xx onto stack.
  • •pop: Remove element on top of stack.
  • •top: Print top element.
  • •getMin: Print minimum element in stack.

Input Format

  • •Line 1: An integer QQ.
  • •Next QQ lines: Commands.

Output Format

Print output for each top and getMin command on a new line.

Example 1:
Input:
6
push -2
push 0
push -3
getMin
pop
getMin
Output:
-3
-2
Explanation: Current min is -3. After popping -3, new min is -2.
Example 2:
Input:
4
push 5
getMin
top
getMin
Output:
5
5
5
Explanation: Single element is both top and minimum.
Example 3:
Input:
5
push 10
push 20
top
getMin
pop
Output:
20
10
Explanation: Top is 20, min is 10.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online