Accepted C++ solution with min-heap.


  • 0
    S

    EDIT: See comments. This solution is not correct.

    NOTE: in this implementation, push is O(log(n)). So this solution is worth discussing with your interviewer, but it may or may not be acceptable.

    class MinStack {
    public:
        /** initialize your data structure here. */
        MinStack() {
            //myStack = new stack<int>();
            //myMinHeap = new priority_queue<int, vector<int>, greater<int> >();
        }
        
        void push(int x) {
            myStack.push(x);
            myMinHeap.push(x);
        }
        
        void pop() {
            int temp =  myStack.top();
            myStack.pop();
            if (temp == getMin()){
                myMinHeap.pop();
            }
        }
        
        int top() {
            return myStack.top();
        }
        
        int getMin() {
            return myMinHeap.top();
        }
    private:
        stack<int> myStack;
        priority_queue<int, vector<int>, greater<int> > myMinHeap;
    };
    

  • 1
    A

    @sasantv This solution is actually wrong.
    Try push 2 -> push 0 -> push 1 -> pop 1 -> pop 0 -> getmin().
    You solution will return 1 as min, but actaully the min is 2 since 1 was popped earlier.


  • 0
    S

    @ayuanx You are right, this shouldn't have passed the tests.


  • 0
    A

    @sasantv If we stick to this method, we have to scan the priority_queue when popping. So every pop will take O(n) time, since the problem doesn't say anything about pop time complexity, it could be accepted, although not very efficient.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.