neetcode-gh / leetcode

Leetcode solutions
MIT License
5.65k stars 2.32k forks source link

Better solution for Min Stack #1266

Open SleeplessChallenger opened 2 years ago

SleeplessChallenger commented 2 years ago

Hey, I created a solution that has O(n) space instead of O(2n) with 2 stacks:

class MinStack:
    def __init__(self):
        self.min_value = float('inf')
        self.stack = list()

    def push(self, val: int) -> None:
        if val < self.min_value:
            self.min_value = val
        self.stack.append((val, self.min_value))

    def pop(self) -> None:
        if self.stack[-1][-1] != self.min_value:
            self.stack.pop()
        else:
            val, min_val = self.stack.pop()
            if len(self.stack) > 0:
                self.min_value = self.stack[-1][-1]
            else:
                self.min_value = float('inf')

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.min_value
NikSWE commented 1 year ago

I would like to modify @SleeplessChallenger's solution a bit more. Here is my version

class MinStack(object):

    def __init__(self):
        self.stack = list()

    def push(self, val):
        minVal = min(val, self.getMin()) if self.stack else val
        self.stack.append((val, minVal))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]