#155. Min Stack

• Solved

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:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

My Solution

---

public class MinStack {
    private Dictionary<int, int> stack;
    private int key;

    public MinStack() {
        stack = new Dictionary<int, int>();
        key = 0;
    }
    
    public void Push(int val) {
        stack.Add(key, val);
        key++;
    }
    
    public void Pop() {
        stack.Remove(key-1);
        key--;
    }
    
    public int Top() {
        return stack[key - 1];
    }
    
    public int GetMin() {
        return stack.Min(s => s.Value);
    }
}

Runtime

592 ms / Beats 5.28%

Memory

54.88 MB / Beats 68.91%

Big O Notation

Time complexity: O(n)
Space complexity: O(n)

Best Solution

---

public class MinStack {
    public Node head;

    public MinStack() {
        
    }
    
    public void Push(int val) {
        if (head == null) 
            head = new Node(val, val, null);
        else 
            head = new Node(val, Math.Min(val, head.min), head);
    }
    
    public void Pop() {
        head = head.next;
    }
    
    public int Top() {
        return head.val;
    }
    
    public int GetMin() {
        return head.min;
    }

    public class Node {
        public int val;
        public int min;
        public Node next;
            
        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

Runtime

1 ms / Beats 97.95%

Memory

53.79 MB / Beats 82.61%

Big O Notation

Time complexity: O(1)
Space complexity: O(n)