Sharing my C++ code and memory limit exceeded problem


  • 0
    Z

    I think almost everyone has came up with the two-stack structure to solve this problem.
    But at the first time, I have got "memory limit exceeded" with following code:

    class MinStack {
    public:
        MinStack() {
            data.clear();
            min_element.clear();
        }
        void push(int x) {
            data.push_back(x);
            if(min_element.empty() || min_element.back() > x)
                min_element.push_back(x);
            else
                min_element.push_back(min_element.back());
        }
    
        void pop() {
            if(data.empty())
                return;
            data.pop_back();
            min_element.pop_back();
        }
    
        int top() {
            return data.back();
        }
    
        int getMin() {
            return min_element.back();
        }
    private:
        deque<int> data;
        deque<int> min_element; //maintain the minimum element
    };
    

    Space complexity is O(2n) because min_element increases simultaneously with data. I believe there must be a "coincident case" which exhausts the memory.

    Then I try to rewrite pop() and push():

    void push(int x) {
        data.push_back(x);
        /*"min_element" push only happens when comes a smaller element.
        Remember the '>=' cannot be '>'.*/
        if(min_element.empty() || min_element.back() >= x)
            min_element.push_back(x);
    }
    
    void pop() {
        if(data.empty())
            return;
        int tmp = data.back();
        data.pop_back();
        /*pop when a current minimum element is pop out.*/
        if(tmp == min_element.back())
            min_element.pop_back();
    }
    

    This time the best space complexity is O(n).

    Hope it will help. Any comment is welcome.


  • 0
    H

    Oh, I meet the same problem, and got Memory Limit Exceeded.
    I use stack<int> and get Accepted.


  • 0
    J

    I do this by adding a counter for the same min_element.


  • 0
    G

    Is your rewrite version get AC? I implement it use linked list and the idea of pop and push is same, but still get MLE


  • 0
    G

    What do you mean by use stack? How do you implement stack?


  • 0

  • 0
    O

    That's funny. I implemented the "stack" by using original c++ linked list with exactly same idea and got the MLE error. I checked here and replace my linked list to some STL container then it AC.


  • 0
    P

    And it's necessary to use deque rather than vector here to avoid MLE.


  • 2
    E

    I had the same problem when use std::vector as the underlying container.
    changing it to std::deque fixed the MLE error.

    Probably the testing program at some point pushes a large number of items onto the stack, causes big memory allocation of the underlying container.

    Becase std::vector requires continguous memory and the STL implementation doubles its size each time a reallocation needed, it will not be able to reuse previous allocated memory. 2^(n+1) > 2^n + 2^(n-1) + .... Thus soon it will have problem to find large enough continguous chunk of memory as the container grows.

    On the other hand, memory allocation of std::deque can be sparse, the space cost is always linear because its memory alocation is not required to be contiguous


  • 0

  • 0
    M

    I have the same problem using linked list to implement my stack. I wish they would release the detail on the failure case, so that we can potentially duplicate the failure ?


Log in to reply
 

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