LeetCode155. Min Stack(OOD)#

📌 Problem Description#

Design a stack (MinStack) that supports the following operations:

push(val): Push an element onto the stack.
pop(): Remove the top element.
top(): Get the top element.
getMin(): Retrieve the minimum element in the stack in O(1) time.

✅ Optimal Approach: Auxiliary Stack (Min Stack)#

Use two stacks:

stack: The regular value stack.
min_stack: Tracks the minimum value at each stage.

Example Workflow:#

push(3)  → stack=[3],     min_stack=[3]
push(2)  → stack=[3,2],   min_stack=[3,2]
push(1)  → stack=[3,2,1], min_stack=[3,2,1]
pop()    → stack=[3,2],   min_stack=[3,2]
getMin() → return 2

Python Implementation:#

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:
        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]

🧩 Alternative Approaches (Keeping O(1) getMin)#

Method	Space Complexity	Notes
Auxiliary stack (above)	O(n)	Most recommended
Store (val, min) tuples	O(n)	Compact, no second stack needed
Difference trick (val - min)	O(n)	Space-saving but complex logic
Min-heap (priority queue)	❌	Does not satisfy O(1) requirement

🧠 OOD (Object-Oriented Design) Recap#

Basic Class and Object Structure:#

class MyClass:
    def __init__(self):
        self.data = []

    def method(self):
        # self refers to the current instance
        self.data.append(1)

Understanding `self`:#

self represents the current object
Variables like self.xxx in __init__() are instance attributes
Always use self.xxx to access or modify instance data within class methods

Method Calling Process:#

obj = MyClass()     # Creates an object, self refers to obj
obj.method()        # Equivalent to MyClass.method(obj)

❗ Common Mistakes#

Type	Description	Example
Using `remove()` to delete min	Removes the first match, not necessarily the top	`self.min_stack.remove(val)` ❌
Using `>` instead of `>=`	Misses duplicate mins	Should use `val <= min_stack[-1]`
Verbose use of `len()` + indexing	Unnecessary complexity	Use `[-1]` and `.pop()` instead

✅ Summary#

The key is to support O(1) retrieval of the current minimum value
The best approach is to maintain an auxiliary stack for minimums
Mastering self and instance state is crucial for solid OOD

LeetCode155. Min Stack(OOD)#

📌 Problem Description#

✅ Optimal Approach: Auxiliary Stack (Min Stack)#

Example Workflow:#

Python Implementation:#

🧩 Alternative Approaches (Keeping O(1) getMin)#

🧠 OOD (Object-Oriented Design) Recap#

Basic Class and Object Structure:#

Understanding self:#

Method Calling Process:#

❗ Common Mistakes#

✅ Summary#

Understanding `self`:#