Python_100DaysofCode/MinStack_Day24.py at main · ayushlingayat/Python_100DaysofCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#Brute Force
class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()

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

    def getMin(self) -> int:
        return min(self.stack)
# Time Complexity:push: O(1)
# pop: O(1)
# top: O(1)
# getMin: O(n)

# 📦 Space Complexity: O(n)
#Better Approach

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack:
            val = self.stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()

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

    def getMin(self) -> int:
        return self.min_stack[-1]

#TC - push: O(1)
# pop: O(1)
# top: O(1)
# getMin: O(1)
#SC -  O(N)

#Optimal Approach

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_val = None

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(val)
            self.min_val = val
        elif val >= self.min_val:
            self.stack.append(val)
        else:
            # Encode the smaller value
            self.stack.append(2*val - self.min_val)
            self.min_val = val

    def pop(self) -> None:
        if not self.stack:
            return
        top = self.stack.pop()
        if top < self.min_val:
            self.min_val = 2*self.min_val - top

    def top(self) -> int:
        top = self.stack[-1]
        if top >= self.min_val:
            return top
        else:
            return self.min_val

    def getMin(self) -> int:
        return self.min_val

# Time Complexity:
# push: O(1)
# pop: O(1)
# top: O(1)
# getMin: O(1)

# 📦 Space Complexity: O(n) — single stack + one variable