Space-efficient and only 1-2 lines per method

  • 1

    I only store:

    • The current min among the stack elements.
    • For each pushed element, the difference to the previous min. If the pushed element changes min, because it is even smaller, then this difference is negative. If it's larger than the previous min, then the difference is positive.

    For pop, I need to pop the last difference and undo its change to min (if any). For top, I need to add the current min and the last difference (if it's positive, i.e., if the last element was larger than the minimum).

    class MinStack:
        def __init__(self):
            self.min = 2 ** 32
            self.diffs = []
        def push(self, x):
            self.diffs += x - self.min,
            self.min = min(self.min, x)
        def pop(self):
            diff = self.diffs.pop()
            self.min -= min(diff, 0)
        def top(self):
            return self.min + max(self.diffs[-1], 0)
        def getMin(self):
            return self.min

Log in to reply

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