Min Stack

Medium
2046.

Min Stack

Min Stack is a medium coding problem on stack, asked in Amazon, Google, Microsoft and Bloomberg interviews.

Design a stack that can also report its smallest element, with every operation in O(1) time. Write the class MinStack:

  • MinStack() creates an empty stack.
  • void push(int x) pushes x onto the stack.
  • void pop() removes the element on top of the stack.
  • int top() returns the element on top of the stack.
  • int getMin() returns the smallest element currently in the stack.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
After pushing -2, 0, -3 the minimum is -3. Popping -3 leaves 0 on top and -2 as the minimum again.

Example 2

Input
["MinStack","push","push","push","getMin","pop","getMin","pop","getMin"] [[],[4],[4],[7],[],[],[],[],[]]
Output
[null,null,null,null,4,null,4,null,4]
Explanation
Duplicates matter: with two 4s on the stack, popping one 4 still leaves a 4, so the minimum stays 4.

Constraints

  • -2^31 <= x <= 2^31 - 1
  • pop, top and getMin are only called on a non-empty stack
  • At most 3 * 10^4 calls are made to push, pop, top and getMin
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var MinStack = function() {
    
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    
};

Sign in to run your own test cases

Sign in

Min Stack — Solution in Python, Java & C++

Min Stack solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Min Stack is a medium coding problem on stack, asked in Amazon, Google, Microsoft and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Stack
  • Asked at: Amazon, Google, Microsoft, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Design a stack that can also report its smallest element, with every operation in O(1) time. Write the class MinStack:

  • MinStack() creates an empty stack.
  • void push(int x) pushes x onto the stack.
  • void pop() removes the element on top of the stack.
  • int top() returns the element on top of the stack.
  • int getMin() returns the smallest element currently in the stack.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation: After pushing -2, 0, -3 the minimum is -3. Popping -3 leaves 0 on top and -2 as the minimum again.

Example 2

Input: ["MinStack","push","push","push","getMin","pop","getMin","pop","getMin"]
[[],[4],[4],[7],[],[],[],[],[]]
Output: [null,null,null,null,4,null,4,null,4]
Explanation: Duplicates matter: with two 4s on the stack, popping one 4 still leaves a 4, so the minimum stays 4.

Constraints

  • -2^31 <= x <= 2^31 - 1
  • pop, top and getMin are only called on a non-empty stack
  • At most 3 * 10^4 calls are made to push, pop, top and getMin

Hints for Min Stack

  1. Hint 1

    Keeping a single "current minimum" variable breaks as soon as the minimum is popped — what was the minimum before it?

  2. Hint 2

    The minimum of the stack depends only on what is below the top, and that never changes while the top is there.

  3. Hint 3

    Store, with every element, the minimum of the stack at the moment it was pushed: min(x, previous minimum). Then getMin reads it from the top entry.

How to solve Min Stack

Push pairs (x, minimum so far). The minimum of a stack is fixed by the elements in it, and the elements below the top never change while the top is in place, so the pair on top always carries the current minimum.

Approach

  1. push(x): push (x, x) if the stack is empty, else (x, min(x, top.min)).
  2. pop(): pop the top pair.
  3. top(): return the top pair's value.
  4. getMin(): return the top pair's minimum.

Why it works

By induction, each pair's stored minimum is the minimum of itself and every element under it. Popping removes a pair without changing the pairs below, whose stored minima were computed from exactly the elements that remain.

Complexity

  • Time — O(1) per operation
  • Space — O(n)

Pitfalls

  • A separate min-stack that only records strictly smaller values breaks on duplicates of the minimum — record <= values, or store the minimum with every element as here.
  • Values span the whole 32-bit range; avoid tricks like storing x - min, which overflow in 32 bits.

Reference solution

Python

class MinStack:

    def __init__(self):
        self.st = []  # pairs (value, minimum of the stack up to here)

    def push(self, x: int) -> None:
        self.st.append((x, min(x, self.st[-1][1]) if self.st else x))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]

Java

class MinStack {
    private Deque<int[]> st = new ArrayDeque<>(); // pairs {value, minimum up to here}

    public MinStack() {
    }

    public void push(int x) {
        st.push(new int[]{x, st.isEmpty() ? x : Math.min(x, st.peek()[1])});
    }

    public void pop() {
        st.pop();
    }

    public int top() {
        return st.peek()[0];
    }

    public int getMin() {
        return st.peek()[1];
    }
}

C++

class MinStack {
    vector<pair<int, int>> st; // {value, minimum up to here}
public:
    MinStack() {}

    void push(int x) {
        st.push_back({x, st.empty() ? x : min(x, st.back().second)});
    }

    void pop() {
        st.pop_back();
    }

    int top() {
        return st.back().first;
    }

    int getMin() {
        return st.back().second;
    }
};

JavaScript

var MinStack = function() {
    this.vals = [];
    this.mins = []; // mins[i] = minimum of vals[0..i]
};

MinStack.prototype.push = function(x) {
    var n = this.mins.length;
    this.vals.push(x);
    this.mins.push(n === 0 ? x : Math.min(x, this.mins[n - 1]));
};

MinStack.prototype.pop = function() {
    this.vals.pop();
    this.mins.pop();
};

MinStack.prototype.top = function() {
    return this.vals[this.vals.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.mins[this.mins.length - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 111 stack problems · the whole catalogue

Learn the technique: Stack Data Structure