Python AC Solution and memory limit exceeded (MLE) problem using tuple element


  • 7
    P

    My AC code:

    class MinStack:
    # @param x, an integer
    def __init__(self):
        # the stack it self
        self.A = []
        self.minS=[]
    # @return an integer
    def push(self, x):
        n=len(self.A)
        if n==0:
            self.minS.append(x)
        else:
            lastmin=self.minS[-1]
            if x<=lastmin:
                self.minS.append(x)
        self.A.append(x)
    # @return nothing
    def pop(self):
        if len(self.A)>0 and self.A.pop()==self.minS[-1]:
            self.minS.pop()
    # @return an integer
    def top(self):
        return self.A[-1]
        
    
    # @return an integer
    def getMin(self):
        return self.minS[-1]
    

    However, at my first try, I use tuples in list [(element, min_value_sofar)] and got MLE. Can anyone explain the reason? I thought that the memory is still O(n).

    My complete solution blog: http://randombet.blogspot.com/2014/09/151-accepted-python-solutions-for_19.html


  • 0
    K
    This post is deleted!

  • -1
    D

    I'm not sure the reason yet but you need to check if the list is empty before you return list[-1] or may lead to an error


  • 0
    P

    Which code are you talking about? I posted my accepted code and asked a question why I can't implement the same algorithm using tuple without MLE.


  • -2
    M

    I think when you use tuple, the space used is 2 * n, because every pushed tuple has 2 items. But use 2 stacks, only when pushed number is less than the current min value, it will be pushed in minStack. So the space used is less than 2n.
    However, I used a one stack solution, which is rewritten from a Java solution that you can find it in another post. I think it will use less memory, but it got MLE error. Who can explain this to me?


  • 0
    L

    I guess the pointer of tuple needs space, so if you use any pointer, it's easy to get MLE.

    There is a clever in the pop method, thanks for sharing this solution.


  • 0
    X

    In this solution, size of minS might be smaller than size of A. So the average space complexity is no more than O(2 * n). Although it's the same as O(n) in big Oh theory, but I think it's treated differently here. BTW thanks for your blog. It's really inspiring.


  • 0
    J

    Hi, i tried you solution but without declaration of n and lastmin in push method. And i get a MLE result. Why is it? Is it possible your solution is almost at the boundary of memory limit?


  • 0
    V

    It seems that your code not only have the MLE problem, but also can't work well without memory limited.
    For push(), every time before you push a x into A, you compare x with the top value in minS, but if x is smaller than the value which is not on the top of minS, it will confuse the order of minS.


  • 0
    P

    The order of minS is exactly the way I want it to be. minS stores the minimal value when it is stored on the top.


  • 0
    V

    Sorry for my mistake, you are right.


  • 0
    O

    Thanks for sharing this. Although it works correctly in my local copy of Python, the Online Judge does not seem to agree. In the test case "push(-1),top,getMin", it gives a very strange output: [-1, -3]. I wonder if anyone knows why.


  • 0
    S

    Very good solution! But I have some troubles to understand "def pop(self)". It seems that you just delete the items in self.minS but not in self.A. Yes?
    And why we should use additional stack to track the min value?
    Thank you!


Log in to reply
 

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