Stack With O(1) Minimum Lookup

medium stack design

Problem

Design a stack supporting push, pop, top, and getMin, all in O(1) time. The trick: keep a parallel min stack whose top is always the minimum among the values currently in the data stack. On push(x), push min(x, currentMin) onto the min stack; on pop, pop both. getMin is just the top of the min stack.

Inputpush 3, push 5, push 2, getMin, pop, getMin

Output2, then 3

Min tracks the running minimum as values come and go.

operations (e.g. "push 3; push 5; push 2; pop; getMin")

class MinStack:
    def __init__(self):
        self.data = []
        self.mins = []
    def push(self, x):
        self.data.append(x)
        m = self.mins[-1] if self.mins else x
        self.mins.append(min(m, x))
    def pop(self):
        self.data.pop()
        self.mins.pop()
    def top(self):
        return self.data[-1]
    def getMin(self):
        return self.mins[-1]

class MinStack {
  constructor() { this.data = []; this.mins = []; }
  push(x) {
    this.data.push(x);
    const m = this.mins.length ? this.mins[this.mins.length - 1] : x;
    this.mins.push(Math.min(m, x));
  }
  pop() { this.data.pop(); this.mins.pop(); }
  top() { return this.data[this.data.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

class MinStack {
    Deque<Integer> data = new ArrayDeque<>();
    Deque<Integer> mins = new ArrayDeque<>();
    public void push(int x) {
        data.push(x);
        int m = mins.isEmpty() ? x : Math.min(mins.peek(), x);
        mins.push(m);
    }
    public void pop() { data.pop(); mins.pop(); }
    public int top() { return data.peek(); }
    public int getMin() { return mins.peek(); }
}

class MinStack {
    vector<int> data, mins;
public:
    void push(int x) {
        data.push_back(x);
        mins.push_back(mins.empty() ? x : min(mins.back(), x));
    }
    void pop() { data.pop_back(); mins.pop_back(); }
    int top() { return data.back(); }
    int getMin() { return mins.back(); }
};

Time: O(1) per op Space: O(n)