🦄 Glimmer MinStack: Constant-Time Min

Difficulty: Intermediate Tags: stack, design, data-structures Series: Data Structures I

Problem

Design a special stack that can: - Push a value onto the stack - Pop a value from the stack - Top - see the top value without removing it - Min - get the minimum value in the stack instantly (O(1) time!)

The challenge: Getting the minimum should be constant time - no matter how many items are in the stack!

Input

data = {
    'ops': list  # List of operations to perform
}

Operations can be: - ['push', x] - push value x onto stack - ['pop'] - remove top element - ['top'] - return top element - ['min'] - return minimum element

Output

list  # Results from 'top' and 'min' operations, in order

Constraints

• 1 ≤ number of operations ≤ 100,000
• All operations are valid (won't pop from empty stack)

Examples

Example 1: Basic MinStack

Input:  {'ops': [['push', 3], ['push', 1], ['min'], ['pop'], ['min']]}
Output: [1, 3]

Step-by-step:

1. push(3)     → Stack: [3]           Min: 3
2. push(1)     → Stack: [3, 1]        Min: 1
3. min()       → Return 1             (output: 1)
4. pop()       → Stack: [3]           Min: 3
5. min()       → Return 3             (output: 3)

Final output: [1, 3]

Example 2: Using Top

Input:  {'ops': [['push', 2], ['push', 5], ['top'], ['min']]}
Output: [5, 2]

Step-by-step:

1. push(2)     → Stack: [2]           Min: 2
2. push(5)     → Stack: [2, 5]        Min: 2
3. top()       → Return 5 (top item)  (output: 5)
4. min()       → Return 2             (output: 2)

Final output: [5, 2]