Min Stack

LeetCode 155 | Difficulty: Medium

Medium

Problem Description

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 the top of the stack.

- `int top()` gets the top element of the stack.

- `int getMin()` retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

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

Constraints:

- `-2^31 <= val <= 2^31 - 1`

- Methods `pop`, `top` and `getMin` operations will always be called on **non-empty** stacks.

- At most `3 * 10^4` calls will be made to `push`, `pop`, `top`, and `getMin`.

Topics: Stack, Design

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

---

Solutions

Solution 1: C# (Best: 144 ms)

Metric	Value
Runtime	144 ms
Memory	34.4 MB
Date	2019-12-27

Solution

public class MinStack {

    private Stack<int> values { get; set; }
    private int _min;

    /** initialize your data structure here. */
    public MinStack()
    {
        values = new Stack<int>();
        _min = Int32.MaxValue;
    }

    public void Push(int x)
    {
        if(x<=_min)
        {
            values.Push(_min);
            _min=x;
        }
        values.Push(x);
    }

    public void Pop()
    {
        if(_min==values.Pop()) _min = values.Pop();
    }

    public int Top()
    {
        return values.Count == 0 ? 0 : values.Peek();
    }

    public int GetMin()
    {
        return values.Count == 0 ? 0 : _min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(x);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.GetMin();
 */

📜 3 more C# submission(s)

Submission (2018-04-08) — 152 ms, N/A

public class MinStack {

    public Stack<int> Values { get; set; }
    public int Min { get; set; }

    /** initialize your data structure here. */
    public MinStack()
    {
        Values = new Stack<int>();
        Min = Int32.MaxValue;
    }

    public void Push(int x)
    {
        if(x<=Min)
        {
            Values.Push(Min);
            Min=x;
        }
        Values.Push(x);
    }

    public void Pop()
    {
        if(Min==Values.Pop()) Min = Values.Pop();
    }

    public int Top()
    {
        return Values.Count == 0 ? 0 : Values.Peek();
    }

    public int GetMin()
    {
        return Values.Count==0 ? 0 : Min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(x);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.GetMin();
 */

Submission (2018-04-08) — 152 ms, N/A

public class MinStack {

    /** initialize your data structure here. */
    public Stack<int> Values { get; set; }
    public Stack<int> Min { get; set; }
    
    /** initialize your data structure here. */
    public MinStack()
    {
        Values = new Stack<int>();
        Min = new Stack<int>();
     
    }

    public void Push(int x)
    {
        Values.Push(x);
        if(Min.Count == 0 || x <= GetMin())
        {
            Min.Push(x);
        }
    }

    public void Pop()
    {
        int popped = Values.Pop();
        if(popped==GetMin())
        {
            Min.Pop();
        }
    }

    public int Top()
    {
        return Values.Count==0 ? 0 : Values.Peek();
    }

    public int GetMin()
    {
        return Min.Count==0 ? 0 :Min.Peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(x);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.GetMin();
 */

Submission (2018-04-09) — 156 ms, N/A

public class MinStack {

    private Stack<int> values { get; set; }
    private int _min;

    /** initialize your data structure here. */
    public MinStack()
    {
        values = new Stack<int>();
        _min = Int32.MaxValue;
    }

    public void Push(int x)
    {
        if(x<=_min)
        {
            values.Push(_min);
            _min=x;
        }
        values.Push(x);
    }

    public void Pop()
    {
        if(_min==values.Pop()) _min = values.Pop();
    }

    public int Top()
    {
        return values.Count == 0 ? 0 : values.Peek();
    }

    public int GetMin()
    {
        return values.Count == 0 ? 0 : _min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(x);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.GetMin();
 */

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• Clarify the expected time complexity for each operation before choosing data structures.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)