How to Design a Stack with constant time in Push, Pop, Top, and GetMin ?

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

This is an data-structure problem that you would need to come up with the best data structures. If using C++, you can use the STL library which provides a good set of data structures such as vector, deque, map, set etc.

The first three operations are trivial if you use a STL::vector type. The key thing to solve this problem is how to you get the Min value of the stack in O(1) constant time? The solution is to allocate another stack for storing the min values. So each time, you remove an element from the main stack, you will also need to remove the last min from the Min stack. Every time you add a new value to the main stack, you will also push the ‘updated’ min to the min stack.

In C++, we can use STL::vector to represent a stack. The push correpsondings to `push_back` method, the pop corresponds to `pop_back` and we can use `back()` to peek the top element in the stack (without removing it from the stack).

The key thing to solve this puzzle is how to get the min value of the stack in O(1). We can use an additional stack to stores the mins. Whenever a new value is about to be pushed to the stack, we push the current min value to the min stack. Popping a value from the stack requires popping the value from the min stack as well.

Here is the C++ solution to this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class MinStack {
public:
    vector<int> data;
    vector<int> mins;
 
    void push(int x) {
        data.push_back(x);
        if (mins.size() == 0) {
            mins.push_back(x);
        } else {
            int min = mins.back(); 
            // push updated min value
            mins.push_back(x < min ? x : min);
        }
    }
 
    void pop() {
        data.pop_back();
        mins.pop_back();
    }
 
    int top() {
        return data.back();
    }
 
    int getMin() {
        return mins.back();
    }
};

class MinStack {
public:
    vector<int> data;
    vector<int> mins;

    void push(int x) {
        data.push_back(x);
        if (mins.size() == 0) {
            mins.push_back(x);
        } else {
            int min = mins.back(); 
            // push updated min value
            mins.push_back(x < min ? x : min);
        }
    }

    void pop() {
        data.pop_back();
        mins.pop_back();
    }

    int top() {
        return data.back();
    }

    int getMin() {
        return mins.back();
    }
};

Stack-Operation-in-C-Programming

You may also like: ACM题解系列之 – 最小堆栈 (Min Stack)

–EOF (The Ultimate Computing & Technology Blog) —