Auxiliary Stack — Track a Second Property

Keep a second stack in sync (mins, maxes, counts) so each push/pop stays O(1) while answering queries about the main stack.

Try this in Python

class MinStack:
    def __init__(self) -> None:
        self.data: list[int] = []
        self.mins: list[int] = []

    def push(self, x: int) -> None:
        self.data.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self) -> None:
        self.data.pop()
        self.mins.pop()

    def min(self) -> int:
        return self.mins[-1]


ms = MinStack()
ms.push(3)
ms.push(1)
ms.push(2)
print(ms.min())
ms.pop()
print(ms.min())

Key takeaways

• Aux stack mirrors the monotonic/min structure of the visible elements.
• For max, mirror with max.
• If you need frequency, pair (value, count) entries.