Min Stack medium

Problem Statement

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

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

Constraints:

• -2<sup>31</sup> <= val <= 2<sup>31</sup> - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output: [null,null,null,null,-3,null,0,-2]

Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Example 2

Input: ["MinStack","push","push","getMin","pop","getMin"] [[], [2147483646], [2147483646], [], [], []]

Output: [null,null,null,2147483646,null,2147483646]

Explanation: MinStack minStack = new MinStack(); minStack.push(2147483646); minStack.push(2147483646); minStack.getMin(); // return 2147483646 minStack.pop(); minStack.getMin(); // return 2147483646

Steps and Explanation

The key to solving this problem efficiently is to use a second stack to track the minimum values encountered so far. We'll have one stack to store the actual values (dataStack) and another to track the minimum values (minStack).

1. push(val): Push the value val onto dataStack. If minStack is empty or val is less than or equal to the top of minStack, push val onto minStack as well. This ensures minStack always contains the minimum value seen up to that point.

2. pop(): Pop the top element from dataStack. If the popped element is equal to the top of minStack, pop from minStack as well to maintain consistency.

3. top(): Return the top element of dataStack.

4. getMin(): Return the top element of minStack.

Code

using System;
using System.Collections.Generic;

public class MinStack
{
    private Stack<int> dataStack;
    private Stack<int> minStack;

    /** initialize your data structure here. */
    public MinStack()
    {
        dataStack = new Stack<int>();
        minStack = new Stack<int>();
    }

    public void Push(int val)
    {
        dataStack.Push(val);
        if (minStack.Count == 0 || val <= minStack.Peek())
        {
            minStack.Push(val);
        }
    }

    public void Pop()
    {
        if (dataStack.Peek() == minStack.Peek())
        {
            minStack.Pop();
        }
        dataStack.Pop();
    }

    public int Top()
    {
        return dataStack.Peek();
    }

    public int GetMin()
    {
        return minStack.Peek();
    }
}

Complexity

• Time Complexity:

  • push(): O(1)
  • pop(): O(1)
  • top(): O(1)
  • getMin(): O(1)

• Space Complexity: O(N), where N is the number of elements in the stack. We use two stacks, each storing up to N elements in the worst case.